Java: Palindrome Finding Taking Too Long; How to Optimize?

This isn't the most optimal way of finding if a string is palindrome or not.

Just loop through n/2 iterations (where n is length of string) and check if character at position i is equal to character at position n-i

If the length of the string s is n then s will be a palindrome if

s[i]=s[n-1-i] for i in range [0,ceil(n/2)]  // 0 based index

Code:

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

It's an algorithm method called "divide and conquer". But in this case is just to make it n/2 instead of n.

Here is a suitable algorithm that might just help :

1.For i = 1 to n/2

2.If string[i] = string[n-1] then continue in the loop

3.Else break and return false

4.return true

If n is the length of the input string, your code takes O(n^2) operations. This may surprise you because there are no nested loops in your code, but both the substring method and the += operator for Strings require the creation of a new String, which requires copying its contents.

To see this in action, I have inserted

System.out.println(s); 

into the isPalindrome() and checkIfPalindrome() methods, and invoked

isPalindrome("doc, note: i dissent. a fast never prevents a fatness. i diet on cod");

This produces the following output:

docnoteidissentafastneverpreventsafatnessidietoncod
ocnoteidissentafastneverpreventsafatnessidietonco
ocnoteidissentafastneverpreventsafatnessidietonco
cnoteidissentafastneverpreventsafatnessidietonc
cnoteidissentafastneverpreventsafatnessidietonc
noteidissentafastneverpreventsafatnessidieton
noteidissentafastneverpreventsafatnessidieton
oteidissentafastneverpreventsafatnessidieto
oteidissentafastneverpreventsafatnessidieto
teidissentafastneverpreventsafatnessidiet
teidissentafastneverpreventsafatnessidiet
eidissentafastneverpreventsafatnessidie
eidissentafastneverpreventsafatnessidie
idissentafastneverpreventsafatnessidi
idissentafastneverpreventsafatnessidi
dissentafastneverpreventsafatnessid
dissentafastneverpreventsafatnessid
issentafastneverpreventsafatnessi
issentafastneverpreventsafatnessi
ssentafastneverpreventsafatness
ssentafastneverpreventsafatness
sentafastneverpreventsafatnes
sentafastneverpreventsafatnes
entafastneverpreventsafatne
entafastneverpreventsafatne
ntafastneverpreventsafatn
ntafastneverpreventsafatn
tafastneverpreventsafat
tafastneverpreventsafat
afastneverpreventsafa
afastneverpreventsafa
fastneverpreventsaf
fastneverpreventsaf
astneverpreventsa
astneverpreventsa
stneverprevents
stneverprevents
tneverprevent
tneverprevent
neverpreven
neverpreven
everpreve
everpreve
verprev
verprev
erpre
erpre
rpr
rpr
p
p

That's quite a wall of text we are asking the computer to compute! We also see that every String is created twice. That's because you needlessly invoke onlyCharacters() in every iteration.

To avoid creating intermediary String instances, you can use a String Builder:

String onlyCharacters(String s) {
    StringBuilder toReturn = new StringBuilder();
    for (Character c : s.toCharArray()) {
        if (Character.isLetter(c)) {
            toReturn.append(c);
        }
    }
    return toReturn.toString();
}

Also, it turns out a StringBuilder has a cool method called reverse(), so we can simplify your program to:

boolean isPalindrome(String s) {
    StringBuilder letters = new StringBuilder();
    for (Character c : s.toCharArray()) {
        if (Character.isLetter(c)) {
            letters.append(c);
        }
    }
    StringBuilder reversedLetters = new StringBuilder(letters).reverse();
    return onlyLetters.equals(reversedLetters);
}

This code only creates 2 StringBuilder objects rather than n Strings, and is therefore about n/2 times faster than your code.

I found this to be faster than any other answer so far:

public class Solution {

  public boolean isPalindrome(String s) {
    for (int low = 0, high = s.length() - 1;; low++, high--) {
      char cLow = 0, cHigh = 0;

      // Find the next acceptable character for the increasing index.
      while (low < high && !Character.isLetterOrDigit(cLow = s.charAt(low))) {
        low++;
      }

      // Find the previous acceptable character for the decreasing index.
      while (low < high && !Character.isLetterOrDigit(cHigh = s.charAt(high))) {
        high--;
      }

      if (low >= high) {
        // All previous character comparisons succeeded and we have a palindrome.
        return true;
      }

      if (Character.toUpperCase(cLow) != Character.toUpperCase(cHigh)) {
        // This is not a palindrome.
        return false;
      }
    }
  }
}

You have only one object: your original String. Every character is tested until we get acceptable characters (Character.isLetter). Then only those are compared.

No temporary object, no superflous checks. Straight to the goal: it does one thing but does it well.

Note: this answers the actual Leetcode OJ answer by checking alphanumerics instead of only letters and by not caring about the case.

You may use this StringBuilder.reverse() to check Palindrome:

    private boolean isPalindrome(String str) {
       StringBuilder strBuilder = new StringBuilder(str);
       return str.equals(strBuilder.reverse().toString());
    }