Longest Palindromic Substring

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(n2) 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

class Solution {
public:
    /*
     * @param s: input string
     * @return: the longest palindromic substring
     */
    string longestPalindrome(string &s) {
        // write your code here
        int len = s.length();
        if (len < 2) {
            return s;
        }

        vector<vector<bool>> dp(len, vector<bool>(len, false));

        int start = 0;
        int end = 0;
        int maxLen =1;

        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        for (int endIndex = 0; endIndex < len; endIndex++) {
            for (int startIndex = 0; startIndex < endIndex; startIndex++) {
                if (endIndex - startIndex == 1) {
                    dp[startIndex][endIndex] = (s[startIndex] == s[endIndex]);
                } else {
                    dp[startIndex][endIndex] = (s[startIndex] == s[endIndex]) && dp[startIndex + 1][endIndex - 1];
                }
                if (dp[startIndex][endIndex]) {
                    int localLen = endIndex - startIndex + 1;
                    if (localLen > maxLen) {
                        maxLen = localLen;
                        start = startIndex;
                        end = endIndex;
                    }
                }
            }
        }

        return s.substr(start, end - start + 1);
    }
};