Longest Palindromic Substring

Dynamic Programming, String

Medium

Question

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(n^2) time is acceptable. Can you do it in O(n) time.

Tags

String

Related Problems

Easy Valid Palindrome 22 % Medium Longest Palindromic Substring 26 % Medium Palindrome Partitioning II 22 %

Analysis

区间类动态规划

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

用dp[i][j]来存DP的状态，需要较多的额外空间: Space O(n^2)

DP的4个要素

• 状态：

  • dp[i][j]: s.charAt(i)到s.charAt(j)是否构成一个Palindrome

• 转移方程：

  • dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])

• 初始化：

  • dp[i][j] = true when j - i <= 2

• 结果：

  • 找 maxLen = j - i + 1;，并得到相应longest substring： longest = s.substring(i, j + 1);

中心扩展

这种方法基本思想是遍历数组，以其中的1个元素或者2个元素作为palindrome的中心，通过辅助函数，寻找能拓展得到的最长子字符串。外层循环 O(n)，内层循环O(n)，因此时间复杂度 Time O(n^2)，相比动态规划二维数组存状态的方法，因为只需要存最长palindrome子字符串本身，这里空间更优化：Space O(1)

Manacher's Algorithm

这种算法可以达到O(n)时间，但是并不很通用，因此这里略过讨论。具体参考：

• Wikipedia: Longest palindromic substring
• Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 1

Solution

区间DP，Time O(n^2) Space O(n^2)

public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
     public String longestPalindrome(String s) {
         if(s == null || s.length() <= 1) {
             return s;
         }

         int len = s.length();
         int maxLen = 1;
         boolean [][] dp = new boolean[len][len];

         String longest = null;
         for(int k = 0; k < s.length(); k++){
             for(int i = 0; i < len - k; i++){
                 int j = i + k;
                 if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])){
                     dp[i][j] = true;

                     if(j - i + 1 > maxLen){
                        maxLen = j - i + 1;
                        longest = s.substring(i, j + 1);
                     }
                 }
             }
         }

         return longest;
     }
}

DP - Time O(n^2), Space O(n^2)

外层循环区间长度，内层循环区间起点

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        String longestPStr = "";
        int strLen = s.length();
        boolean[][] dp = new boolean[strLen][strLen];
        for (int len = 1; len <= strLen; len++) {
            for (int i = 0; i < strLen; i++) {
                int j = i + len - 1;
                if (j >= strLen) {
                    break;
                }
                dp[i][j] = (len <= 2 || dp[i + 1][j - 1]) && s.charAt(i) == s.charAt(j);
                if (dp[i][j] && len > longestPStr.length()) {
                    longestPStr = s.substring(i, j + 1);
                }
            }
        }
        return longestPStr;
    }
}

*Another implementation DP - Time O(n^2), space O(n^2)

外层循环区间起点，内层循环区间终点

递推公式中可以看到，首先知道了 i + 1 才会知道 i ，所以只需要倒着遍历i就行了。

类似的，先知道j - 1才知道j，因此顺着遍历j

In the state transfer function: j - i < 2 could also be j - i <= 2

public String longestPalindrome(String s) {
    int n = s.length();
    String res = "";
    boolean[][] dp = new boolean[n][n];

    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]); //j - i 代表长度减去 1

            if (dp[i][j] &&  j - i + 1 > res.length()) {
                res = s.substring(i, j + 1);
            }
        }
    }
    return res;
}

Space Optimized DP - Time O(n^2), space O(n)

public String longestPalindrome7(String s) {
        int n = s.length();
        String res = "";
        boolean[] P = new boolean[n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= i; j--) {
                P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
                if (P[j] && j - i + 1 > res.length()) {
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }

Expand Around Center - Time O(n^2) Space O(1)

public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
    public String longestPalindrome(String s) {
            if (s == null || s.length() <= 1) {
                return s;
            }

            String longest = s.substring(0, 1);
            for (int i = 0; i < s.length(); i++) {
                // get longest palindrome with center of i
                String tmp = helper(s, i, i);
                if (tmp.length() > longest.length()) {
                    longest = tmp;
                }

                // get longest palindrome with center of i, i+1
                tmp = helper(s, i, i + 1);
                if (tmp.length() > longest.length()) {
                    longest = tmp;
                }
            }

            return longest;
    }

    // Given a center, either one letter or two letter,
    // Find longest palindrome
    public String helper(String s, int begin, int end) {
        while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
            begin--;
            end++;
        }
        return s.substring(begin + 1, end);
    }
}

Another expand-center implementation

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }

        String longest = "";

        for (int i = 0; i < s.length(); i++) {
            // single center
            String tmp = helper(s, i, i);
            if (tmp.length() > longest.length()) {
                longest = tmp;
            }

            // dual center
            tmp = helper(s, i, i + 1);
            if (tmp.length() > longest.length()) {
                longest = tmp;
            }

        }
        return longest;
    }

    // center expand helper function
    // @return longest string centered at i, j
    private String helper(String s, int i, int j) {
         if (i >= s.length() || j >= s.length()) {
             return "";
         }
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }
        return s.substring(i + 1, j);
    }
}

Expand Center - O(n^2) time, O(1) space

@jinwu

7 ms, faster than 99.69%

public class Solution {
private int lo, maxLen;

public String longestPalindrome(String s) {
    int len = s.length();
    if (len < 2)
        return s;

    for (int i = 0; i < len-1; i++) {
         extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
         extendPalindrome(s, i, i+1); //assume even length.
    }
    return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
    while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
        j--;
        k++;
    }
    if (maxLen < k - j - 1) {
        lo = j + 1;
        maxLen = k - j - 1;
    }
}}

Reference

• LeetCode Discussion
• *programcreek: Longest Palindromic Substring (Java)
• 水中的鱼: Longest Palindromic Substring 解题报告