# Longest palindrome in a string

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

• MathJax usage will always earn a +1 from me! :) – syb0rg Apr 14 '14 at 22:11
• related: codegolf.stackexchange.com/q/16327/152. Just avoid any techniques you find there, and you will be fine. – AShelly Apr 15 '14 at 13:40
• i think you should use char [] instead of performing operation in string. because String is internally having char array and its faster. – Prashant Jan 23 '15 at 13:13

# 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....

• O(n2) is possible if you look for palindromes centered on i. That's j != i--not 1. Though I don't know exactly why j is allowed to pass i to the left; it will check each substring twice unless I read it too quickly. – David Harkness Apr 15 '14 at 1:02
• String.substring() is also an O(n) operation starting with Java 7. – 200_success Apr 15 '14 at 3:30
• @200_success Time for Substring { String whole, int start, int length }? ;) Was this chosen because the greater safety outweighted the diminishing cost of copying memory? – David Harkness Apr 15 '14 at 3:45
• @DavidHarkness When substrings share the memory of the parent string, the existence of a reference to any substring will prevent the entire parent string from being garbage-collected. It was decided that allowing such memory leaks to be fixed was more important than O(1) .substring() performance. – 200_success Apr 15 '14 at 3:55

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.

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(n2) 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 ...
}

• I think longestOf(String ... vals) would make things smoother. longestOf(longest, longestOdd, longestEven) is more readable. – Cruncher Apr 15 '14 at 14:37

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

• Efficient parsing often requires having weird overlapping loops which can't necessarily be split up. I haven't worked out an efficient design for the palindrome searching in particular, but in many cases a loop will have to index over several things until a condition is met, and multiple indices' values will be relevant at that time. Since Java has neither ref parameters, nor an efficient means of returning multiple values, in many situations the only ways to make parsing efficient will be to define a class to hold multiple loosely-associated values and pass that to the function, or else... – supercat Apr 18 '14 at 17:30
• ...put the parsing loops within the method that "calls" them. Personally, I think Java's thread class should have included a few general-purpose fields of type long and object which could be used to return multiple values. Using names like currentThread.long1, currentThread.long2, etc. would be icky, but still less clunky than creating aggregate data holders for the purpose. – supercat Apr 18 '14 at 17:34

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.