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

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

StackExchange Code Review Q#47181, answer score: 15