Longest palindrome in a string

Question

Please be brutal, and judge my code as if it was written at a top 3 tech company, straight out of college. (The method signature, and input parameter is given by the problem, so don't worry about that)

Worst case complexity: \$ O \left( n^2 \right) \$

Space complexity: \$ O \left( n \right) \$

Time it took me to solve this:
6 minutes (I got it right the first shot, and passed all the test cases)

Problem:

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

---

  public String longestPalindrome(String s) {
        String longestPalindrome = "";
        for(int i = 0; i < s.length(); i++){
            for(int j = s.length()-1; j >= 0 && j != i; j--){
                if(isPalindrome(s.substring(i,j+1))){
                    if(s.substring(i, j+1).length()>longestPalindrome.length()){
                        longestPalindrome = s.substring(i, j+1);
                        return longestPalindrome;
                    }
                }
            }
        }
        return longestPalindrome;
    }
    public boolean isPalindrome(String s){
        int end = s.length()-1;
        for(int i=0; i<s.length()/2; i++){
            if(s.charAt(i)!=s.charAt(end)){
                return false;
            }
            end--;
        }
        return true;
    }

Answer 1

Complexity

Your answer is \$O(n^3)\$ and not \$O(n^2)\$. You have three levels of nested loops... two inside the longestPalindrome() method and another inside the isPalindrome().

Can this problem be solved with less complexity? I believe it is possible to do an \$O(n^2)\$ solution ... I'll have to think it through though.

Test-Cases

Your code may have passed the test cases, but I don't believe your code works every time... consider this:

                if(s.substring(i, j+1).length()>longestPalindrome.length()){
                    longestPalindrome = s.substring(i, j+1);
                    return longestPalindrome;
                }

You return the first palindrome you find.... longestPalindrome starts off as the empty String (length 0), and you return the first value that is longer. Your code could simply be equally broken as:

   if(s.substring(i, j+1).length() > 0){
       return s.substring(i, j+1);
   }

I don't know what the test cases are, but they need work.

Nit-picks

• giving a variable the same name as a method is 'wrong'... : longestPalindrome

• you calculate s.substring(i, j+1) three times in the following block:

         if(isPalindrome(s.substring(i,j+1))){
             if(s.substring(i, j+1).length() > longestPalindrome.length()){
                 longestPalindrome = s.substring(i, j+1);
                 return longestPalindrome;
             }
         }
  

Performance

Your loops could be trimmed down (a lot). These optimizations do not affect the complexity, but they do reduce the computational overhead:

for(int j = s.length()-1; j >= 0 && j != i; j--){

has redundant j-conditions. The j >= 0 can be dropped since the j != 1 will be encountered first.

Also, j is only ever used in a +1 context. You may as well change the loop conditions to be:

       for(int j = s.length(); j > i; j--){

and then replace all the j + 1 references inside the loop with plain j.

Conclusion

I am not satisfied that this solution reliably finds the longest palindrome....

Answer 2

Your implementation doesn't pass some unit tests:

// actual: "aba"
Assert.assertEquals("aaaa", longestPalindrome("abaaaa"));

---

In your isPalindrome method, I would drop the end variable, since the same thing can be derived from the length of the string anyway:

if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
    return false;
}

Instead of having 2 counting variables that go in opposite directions (i and end), I think it's more robust to have just one.

---

Time it took me to solve this:

6 minutes (I got it right the first shot, and passed all the test cases)

This is "mostly" irrelevant in terms of code review. "Mostly", because if somebody tells me this, I would ask them to double-check again carefully before I review something that was done in a hurry and might be rubbish. In particular I would ask first:

• Have you covered your solution with unit tests?
• Are you sure you covered all corner cases?
• Have you decomposed your solution to small logical units?
• Did you use your IDE to automatically format your code nicely?

It's not very nice to ask anybody to review something you put together fast, without carefully checking these things first.

And, if you make such statements in a submission for a job interview, you will probably come off as a show-off and not get the job. Cover your back with unit tests, do the best you can, and submit in a humble manner. If they want to know how fast you did it, they will ask.

Answer 3

You have the same formatting inconsistencies I pointed out in a previous question. Take two more minutes to fix these before committing (submitting code). Feel free to use your editor's autoformat command for CR.

Store reused expressions in aptly-named local variables. Not only do you avoid possibly-expensive recalculations but also improve code readability. @rolfl touched on this for the substrings, but it even applies to quick calls to s.length() which you use several times.

As I mentioned in a comment, you can achieve O(n²) by looking for palindromes centered on i. It's tricky because you must handle both odd- and even-length palindromes, but it will be faster.

The loop terminus in isPalindrome should be i < end. And combine the two "step" expressions since they are logically related: i++, end--.

Edit

One often-overlooked advantage of extracting small one-time-use methods is that you get documented local variables for free.

public static final NONE = "";

public String longestPalindrome(String s) {
    String longest = NONE;
    for (int i = 0, len = s.length(); i < len; i++) {
        longest = longerOf(longest, 
                           longerOf(longestOddPalindrome(s, i, len), 
                                    longestEvenPalindrome(s, i, len));
    }
    return longest;
}

private String longestOdd(String s, int center, int len) {
    return longestPalindrome(s, center, center, len);
}

private String longestEven(String s, int center, int len) {
    if (center < len - 1 && s.charAt(center) == s.charAt(center + 1) {
        return longestPalindrome(s, center, center + 1, len);
    }
    else {
        return NONE;
    }
}

private String longest(String s, int left, int right, int len) {
    do {
        left--;
        right++;
    } while (left >= 0 && right < len && s.charAt(left) == s.charAt(right));
    return s.substring(left + 1, right - left - 1);
}

private String longerOf(String left, String right) {
    return left.length() > right.length() ? left : right;
}

Refactor

If you return NONE if left or right start outside the bounds in longest(String, int, int, int), longestEven becomes a one-liner like longestOdd, and both can be moved into the public method without much loss of clarity.

public String longestPalindrome(String s) {
    String longest = NONE;
    for (int i = 0, len = s.length(); i < len; i++) {
        longest = longerOf(longest, 
                           longerOf(longestPalindrome(s, i, i, len), 
                                    longestPalindrome(s, i, i + 1, len));
    }
    return longest;
}

private String longest(String s, int left, int right, int len) {
    if (left < 0 || right >= len) {
        return NONE;
    }
    do ...
}

Answer 4

Most brutal comment to my disposal: No raw loops. Every loop does a particular job, and such job deserves a proper name. If it doesn't, the loop has no right to exist. My solution (untested; looks for the length not the palindrome itself; hope you got an idea):

int growPalindromeOdd(String s, int i) {
    int delta = 0;
    while ((i - delta >= 0) && (i + delta) < s.length())
        if (s[i - delta] == s[i + delta])
            delta += 1;
    return 1 + delta*2;
}

int growPalindromeEven(String s, int i) {
    int delta = 0;
    while ((i - delta >= 0) && (i + 1 + delta) < s.length())
        if (s[i - delta] == s[i + 1 + delta])
            delta += 1;
    return delta * 2;
}

int findLongestPalindromeLength(String s) {
    int maxlength = 0;
    int i = 0;
    while (i < s.length()/2) {
        int no = growPalindromeOdd(s, i);
        if (no > maxlength) maxlength = no;
        int ne = growPalindromeEven(s, i);
        if (ne > maxlength) maxlength = ne;
    }
}

Answer 5

What's the longest palindrome in "War and Peace"? I bet it's not very long. But if you look for the longest palindrome in a book of just a million characters, you are checking about 500 billion substrings.

Iterating over the characters that could be at the centre of palindromes, as others suggested, will work very well with your average text, like War and Peace.

If someone specifically designs input to make this slow, they would create huge numbers of consecutive equal characters, like xaaaaaaaaaaaaax, or consecutive alternating characters, like xababababababababx, so that at almost every index we would find a very long palindrome. To handle this, split the text into sequences of identical characters or sequences of alternating characters. (And you must have at least two consecutive or three alternating characters in a row for a palindrome of two or three characters). So for example, when we find a sequence of 1,000,000 characters ababab...ab (but not a million and one) then we have a palindrome of length 999,999. If we find 1,000,001 characters abab...aba, then we already have a palindrome of length 1,000,001 which might be lengthened depending on the characters around it. We don't have to check for palindromes around each of these characters, because the longest palindrome will start in the middle of that sequence. Similar with a large number of consecutive identical letters, except both even and odd numbers work.