Skip to content

5 Longest Palindromic Substring

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.

Thoughts:

Trivial way is to calculate each substring is palindrome, using O(n^2) time and space. Could be optimized using only O(1) space. Idea is to return the longest palindromic substring that is center by (i,i) or (i, i + 1).

Solution:

Trivial way:

public class Solution {
    public String longestPalindrome(String s) {
        boolean[][] isPa = new boolean[s.length()][s.length()];
        calIsPa(isPa, s);
        String longest = "";
        int max = 0;
        for (int i = 0; i < s.length(); i ++){
            for (int j = i; j < s.length(); j ++){
                if (isPa[i][j] == true && (j - i + 1) > max){
                    max = j - i + 1;
                    longest = s.substring(i, j + 1);
                }
            }
        }
        return longest;
    }
    private void calIsPa(boolean[][] isPa, String s){
        for (int i = 0; i < s.length(); i ++){
            isPa[i][i] = true;
        }
        for (int i = 0; i < s.length() - 1; i ++){
            if (s.charAt(i) == s.charAt(i+1)){
                isPa[i][i+1] = true;
            }
        }
        for (int l = 3; l <= s.length(); l ++ ){
            for (int i = 0; i < s.length() - l + 1; i ++){
                if (s.charAt(i) == s.charAt(i + l - 1) && isPa[i+1][i + l -2]){
                    isPa[i][i+ l - 1] = true;
                }
            }
        }
    }

}
The better way:

public class Solution {
    public String longestPalindrome(String s) {
        String longest = "";
        for (int i = 0; i < s.length(); i ++){
            String tmp = "";
            tmp = paCenterBy(s, i, i);
            if (tmp.length() > longest.length()){
                longest = tmp;
            }
            tmp = paCenterBy(s, i, i + 1);
            if (tmp.length() > longest.length()){
                longest = tmp;
            }
        }  
        return longest;
    }
    private String paCenterBy(String s, int cleft, int cright){
        String result = "";
        while (cleft >=0 && cright < s.length() && s.charAt(cleft) == s.charAt(cright)){
            cleft --;
            cright ++;
        }
        return s.substring(cleft + 1, cright);
    }
}