Palindrome tester

Question

This program takes lines of input. The first line is an int specifying how many further lines will be input. For the following lines (comprised of characters a-z), it will be determined whether removing one character from the line can result in the line being a palindrome.

I know this can be substantially improved, but I don't know how. Could I somehow capitalize on the fact that only characters a-z are used?

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        try {
            int cases = Integer.parseInt(br.readLine());

            for (int i = 0; i < cases; i++) {
                System.out.println(canBePalindrome(br.readLine()) ? "YES" : "NO");
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static boolean canBePalindrome(String line) {
        if (line.length() <= 1) {
            return false;
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < line.length(); i++) {
            if (isPalindrome(sb.append(line).deleteCharAt(i).toString())) {
                return true;
            }

            sb.setLength(0);
        }
        return false;
    }

    private static boolean isPalindrome(String line) {
        return line.equals(new StringBuilder(line).reverse().toString());
    }
}

Answer 1

main()

Your main function looks good, except for the catch-all exception handler. It leaves me wondering what sorts of exceptions might be lurking in the code. I believe you are mainly concerned with IOException, so just catch those. Better yet, just declare main(String[] args) throws IOException, as the built-in behaviour is to print a stack trace and abort.

The class could be better named. I suggest PalindromeChecker instead of Main.

isPalindrome()

That is a straightforward "brute-force" implementation — a direct translation of the task into code. It has some virtues, but performance is not one of them.

Here is an algorithm that could work faster, since it involves no new objects:

public static boolean isPalindrome(String s) {
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
        if (s.charAt(i) != s.charAt(j)) {
            return false;
        }
    }
    return true;
}

canBePalindrome()

The method name leaves me puzzled as to how it differs from isPalindrome(). I suggest renaming it to isAlmostPalindrome().

You could implement it using a variant of the algorithm above.

public static boolean isAlmostPalindrome(String s) {
    int i, j;

    int fuzz = 0;
    for (i = 0, j = s.length() - 1; i < j; i++, j--) {
        if (s.charAt(i) != s.charAt(j)) {
            if (++fuzz < 1) {
                j++; // Pretend to delete charAt(i)
            } else {
                break;
            }
        }
    }
    if (fuzz == 1 || (i == j && fuzz == 0)) {
        return true;
    }

    // The code below is identical to the code above except for the one commented line

    fuzz = 0;
    for (i = 0, j = s.length() - 1; i < j; i++, j--) {
        if (s.charAt(i) != s.charAt(j)) {
            if (++fuzz < 1) {
                i--; // Pretend to delete charAt(j)
            } else {
                break;
            }
        }
    }

    return false;
}

But wait… repeating code like that is kind of nasty. We can do better, I think.

private static boolean isPalindrome(String s, int firstIndex, int lastIndex) {
    for (int i = firstIndex, j = lastIndex; i < j; i++, j--) {
        if (s.charAt(i) != s.charAt(j)) {
            return false;
        }
    }
    return true;
}

public static boolean isPalindrome(String s) {
    return isPalindrome(s, 0, s.length() - 1);
}

public static boolean isAlmostPalindrome(String s) {
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
        if (s.charAt(i) != s.charAt(j)) {
            return isPalindrome(s, i + 1, j)
                || isPalindrome(s, i, j - 1);
        }
    }

    // Exact palindrome. Any palindrome is also an almost-palindrome,
    // by deleting one of the middle characters.
    return true;
}

Answer 2

A common quiz question is to check if a string is a palindrome without using in-built reverse functions. In Java, this can be done as follows:

static boolean isPalindrome(String target) {
    char[] targetChars = target.toCharArray();
    int length = targetChars.length;

    for (int start = 0, end = length - 1; start < end ; start++, end--) {
        if (targetChars[start] != target[end]) {
            return false;
        }
    }

    return true;
}

This can be further modified to support your use case: checking if removing a single character will make the string a palindrome. Instead of failing when a character doesn't mirror the opposite position in the string, look ahead and behind to see if the next character will match. If so, increment a counter and continue. If the counter is equal to the number of occurrences expected (1) then the result is true.

static boolean isOneOffFromPalindrome(String target) {
    char[] targetChars = target.toCharArray();
    int length = targetChars.length;
    int removedChars = 0;

    for (int start = 0, end = length - 1; start < end && removedChars < 2; start++, end--) {
        if (targetChars[start] != targetChars[end]) {
            if (targetChars[start + 1] == targetChars[end]) {
                removedChars++;
                start++;
            } else if (targetChars[start] == targetChars[end - 1]) {
                removedChars++;
                end--;
            } else {
                return false;
            }
        }
    }

    return removedChars == 1 || removedChars == 0 && length % 2 == 1;
}

Answer 3

Here's a suggestion for improvement of the key method. There is a single pass through the string as far as required, which is still in O(N) run time.

null string is considered a palindrome. It keeps track of one allowed character deletion in two boolean variables, one for right-to-left scan and one for left-to-right scan.

public class CodeReview {
static boolean palindromeMinusOneChar(String str) {
    if (str == null) return true;
    char[] a = str.toCharArray();
    boolean deletedRtl = false, deletedLtr = false; // no deletions yet
    boolean rtlMatch = true, ltrMatch = true;       // assume success

    for (int lRtl = 0, rRtl = a.length - 1, lLtr = lRtl, rLtr = rRtl; 
            lRtl < rRtl && lLtr < rLtr; 
            lRtl++, rRtl--, lLtr++, rLtr--) {
        if (lRtl >= rRtl && a[lRtl] != a[rRtl] && !deletedRtl) {
            deletedRtl = true;
            if      (a[lRtl] == a[rRtl-1]) rRtl--;  // delete from right
            else if (a[lRtl+1] == a[rRtl]) lRtl++;  // delete from left
            else rtlMatch = false;                  // can't delete -> RTL scan fails
        }
        if (lLtr >= rLtr && a[lLtr] != a[rLtr] && !deletedLtr) {
            deletedLtr = true;
            if      (a[lLtr+1] == a[rLtr]) lLtr++;  // delete from left
            else if (a[lLtr] == a[rLtr-1]) rLtr--;  // delete from right
            else ltrMatch = false;                  // can't delete -> LTR scan fails
        }
        if (!rtlMatch && !ltrMatch)
            return false;                           // both RTL and LTR were deleted
    }
    return true;                                    // rtlMatch || ltrMatch
} // method
} // class

Tested with

import org.junit.*;
import static org.junit.Assert.*;

public class TestCodeReview {
@Test
public void palindromeMinusOneChar()
{
    assertTrue(CodeReview.palindromeMinusOneChar("abax"));
    assertTrue(CodeReview.palindromeMinusOneChar("hannah"));
    assertTrue(CodeReview.palindromeMinusOneChar("abcbbca"));
    // etc.
} // method
} // class