Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S.

S[i...j] where 0 <= i <= j < len(S)

A string which reads the same backwards. More formally, S is palindrome if reverse(S) = S.

Incase of conflict, return the substring which occurs first ( with the least starting index ).

Input : "aaaabaaa"
Output : "aaabaaa"

Method 1:

DP. 

Consider the case “ababa”. If we already knew that “bab” is a palindrome, it is obvious that “ababa” must be a palindrome since the two left and right end letters are the same.

Stated more formally below:

Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.
Therefore,

P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj )
The base cases are:

P[ i, i ] ← true
P[ i, i+1 ] ← ( Si = Si+1 )
This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on…

Solution:

Time: O(n^2)
Space: O(n^2)

public class Solution {
    public String longestPalindrome(String A) {
        int n = A.length();
        boolean[][] isP = new boolean[n][n];
        for (int i = 0; i < n; i ++) {
            isP[i][i] = true;
            if (i + 1 < n && A.charAt(i) == A.charAt(i + 1)) {
                isP[i][i + 1] = true;
            }
        }
        // p[i][j] = true if p[i + 1][j - 1] && A[i] == A[j]
        for (int j = 2; j < n; j ++) {
            for (int i = 0; i < n; i ++) {
                if ((i + j) < n && isP[i + 1][i + j - 1] && A.charAt(i) == A.charAt(i + j)) {
                    isP[i][i + j] = true;
                }
            }
        }
        int start = 0;
        int end = 0;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                if (isP[i][j] && (j - i) > (end - start)) {
                   start = i;
                   end = j;
                }
            }
        }
        return A.substring(start, end + 1);
    }
}

Method 2:

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2N-1 such centers.

You might be asking why there are 2N-1 but not N centers?

The reason is that the center of a palindrome can be in between two letters.

Such palindromes have even number of letters (such as “abba”) and their center are between the two ‘b’s.

Since expanding a palindrome around its center could take O(N) time, the overall complexity is O(N2).

Solution:

Time: O(n^2)
Space: O(1)

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i); //从一个字符扩展
        int len2 = expandAroundCenter(s, i, i + 1); //从两个字符之间扩展
        int len = Math.max(len1, len2);
        //根据 i 和 len 求得字符串的相应下标
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

Method 3:

Solution:

Time: O(n)
Space: O(n)

public class Solution {
    public String longestPalindrome(String A) {
        String str = processed(A);
        int[] p = new int[str.length()];
        int C = 0, R = 0;
        for (int i = 1; i < str.length() - 1; i ++) {
            int iMirror = 2 * C - i;
            if (i < R) {
                p[i] = Math.min(R - i, p[iMirror]);
            } else {
                p[i] = 0;
            }
            // expand from R + 1, this won't do anything if p[i] == p[iMirror]
            // this while loop will run at most n times because i + p[i] or R increases 
            // monotinically
            while (str.charAt(i + p[i] + 1) == str.charAt(i - p[i] - 1)) {
                p[i]++;
            }
            if (i + p[i] > R) {
                C = i;
                R = i + p[i];
            }
        }
        int maxLen = 0;
        for (int i = 0; i < p.length; i ++) {
            if (p[i] > maxLen) {
                maxLen = p[i];
                C = i;
            }
        }
        int start = (C - maxLen) / 2;
        return A.substring(start, start + maxLen);
    }
    
    private String processed(String A) {
        StringBuilder sb = new StringBuilder("^#");
        for (int i = 0; i < A.length(); i ++) {
            char c = A.charAt(i);
            sb.append(c);
            sb.append("#");
        }
        sb.append("$");
        return sb.toString();
    }
}