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());
 }
}

• RubberDuck: I don't understand this code. You should have been done at isPalindrome. What exactly are you trying to accomplish? Also, any string of length 1 is the same forward and backward, hence, a palindrome.
• Joel Christophel: canBePalindrome() checks whether removing one character from the String can create a palindrome. isPalindrome checks if a String is a palindrome. Admittedly, the method name isn't the best, but everything should be obvious from the specs I provided.
• psaxton: This is code review. Expect to receive comments about your naming conventions. Regarding your question about capitalizing on the fact that only chars a-z are being provided, you are already doing that in not being case insensitive. Unless the spec states that lines containing characters outside that range should fail, you will only hurt performance by checking.
• Andrej: Thanks, @200_success. Based on Ixanezis's test case that pointed out missing left-to-right first removal scenario I added another parameter and a wrapper method that checks both scenarios. Thanks, Ixanezis, for pointing out this issue.

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;
}

• psaxton: When an odd length string is a palindrome, the middle character can be removed and still remain a palindrome. I updated my code to allow for that condition.
• Joel Christophel: It seems like an initial if(isPalindrome(s) && s.length() % 2 == 1) return true should do it.
• psaxton: Be sure to write some test cases. 200_success and I have lead you to water and held your head under. If you're not going to drink, then I'm going fishing :)
• Joel Christophel: Thanks for the time both of you have put into your answers. You've clearly demonstrated the sort of changes that can be made to improve code efficiency.
• psaxton: @vixen If i == j than s.charAt(i) == s.charAt(j). There is no need to check.

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;
}

• Joel Christophel: I appreciate you sharing how to combine the two methods into one.
• psaxton: @JoelA.Christophel Thank you. I'm honestly not sure how to separate it from this form.
• Joel Christophel: In order to improve efficiency, couldn't you return false upon entering if (targetChars[start] != targetChars[end]) a second time?
• psaxton: I would have to profile the code to know for sure. This optimization would be dubious at best, because in the end it is just changing the order of the conditional branch -- copying the else condition to the top to check if removedChars == 1. The else block would need to remain on the bottom in the case that both look-ahead checks fail. The end result is that you're adding one more condition check to save from 2 condition checks.
• Joel Christophel: Disregard my last comment. However hannah fails using your algorithm.

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

• Ixanezis: The approach is worth to be noted, however, the code is easy to break down: it's getting wrong result on "abcbbca" string: ideone.com/sux6OP
• Andrej: Great catch. Thank you. Code above is modified to account for the missing left-to-right first scenario.
• Andrej: Also on ideone.com/BcjiVa. Very useful online IDE.
• Ixanezis: Well, now you would replace the 4 most inner ifs with just r++ and l-- respectively and come up to the code very much alike the one of @200_success. Not saying that boolean rtl argument is probably what most people wouldn't consider beautiful :)
• Andrej: Here is a different idea. Single pass through the string looking for both possible right-to-left as well as left-to-right single character deletions. I've updated the code and added a simple unit test to go with it. While run time is still not better than O(N), it preserves the original single for loop approach.