Longest Palindromic Substring

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.

Example

Given the string = "abcdzdcab", return "cdzdc".

Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

DP Solution:

1. State: f[i][j] substring(i, j) is palindrome or not
2. Function:
   1. f[i][j-1] = true iff s[i] = s[j-1] and f[i-1][j] == true
   2. f[i][j] = true iff s[i] = s[j] and f[i-1][j+1] == true
   3. f[i][i+1] = true when s[i] == s[i+1]
   4. calculate the max
3. Initialize: f[i][i] = true
4. Answer: max

    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        int n = s.length();
        int[][] f = new int[n][n];
        f[0][0] = 1;
        int maxLength = 1;
        String max = s.substring(0, 1);
        for(int i = 1; i < n; ++i) {
            f[i][i] = 1;
            if (s.charAt(i) == s.charAt(i-1)) {
                f[i-1][i] = 1;
                if (maxLength < 2) {
                    maxLength = 2;
                    max = s.substring(i-1, i+1);    
                }
            }

            int j = i-1;
            while(j >= 0) {
                if (f[j][i-1] == 1 && j > 0 && s.charAt(j-1) == s.charAt(i)) {
                    f[j-1][i] = 1;
                    if (maxLength < i-j+2) {
                        maxLength = i-j+2;
                        max = s.substring(j-1, i+1);    
                    }
                } else if(f[j+1][i-1] == 1 && s.charAt(j) == s.charAt(i)) {
                    f[j][i] = 1;
                    if (maxLength < i-j+1) {
                        maxLength = i-j+1;
                        max = s.substring(j, i+1);    
                    }
                }
                j--;
            }
        } 

        return max;
    }

Normal Solution:

1. Consider ODD and EVEN
2. extend from central point to get the max palindrome
3. time: O(n^2)

    private int start = 0;
    private int maxLength = 1;
    public String longestPalindrome1(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        int n = s.length();
        for(int i = 0; i < n-1; ++i) {
            getPalindrome(s, i, i);
            getPalindrome(s, i, i+1);
        }

        return s.substring(start, start+maxLength);
    }

    private void getPalindrome(String s, int l, int r) {
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }

        if (maxLength < r-l-1) {
            maxLength = r-l-1;
            start = l+1;
        }
    }