# 5. 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.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

# Solution

Approach 1: Longest Common Substring and then check the substring's indices.

Approach 2: Starting from both the head and tail of the array, we compare each pair of characters towards each other (Time Limit Exceeded).

Approach 3: Starting from the middle of the array, we compare each pair of characters towards the reversed directions.

Approach 4: Dynamic programming.

Approach 5: Manacher's Algorithm: http://articles.leetcode.com/longest-palindromic-substring-part-ii/

# Code (Python)

Approach 4:

    def longestPalindrome(self, string):
        # idea: DP. is_palindrome[i][j] -- string[i:j+1] is a palindrome
        # O(N^2) time, O(N^2) space
        if not string:
            return ''
        longest_substring = string[0]
        is_palindrome = [[False for _ in range(len(string))] for _ in range(len(string))]
        for span in range(len(string)):
            for start in range(len(string)):
                end = start + span
                if end >= len(string):
                    break
                if span == 0:
                    is_palindrome[start][end] = True
                elif span == 1:
                    is_palindrome[start][end] = (string[start] == string[end])
                else:
                    is_palindrome[start][end] = is_palindrome[start+1][end-1] if string[start] == string[end] else False
                if is_palindrome[start][end] and end - start + 1 > len(longest_substring):
                    longest_substring = string[start:end+1]
        return longest_substring

Approach 5:

    def longestPalindrome(self, string):
        # idea: for each char in string, expand outwards to search for the longest palindrome
        # O(N^2) time, O(1) space
        if not string:
            return ''
        longest_substring = string[0]
        for i in range(len(string)):
            longest = self._longest(string, i, i)
            if len(longest) > len(longest_substring):
                longest_substring = longest
            if i < len(string) - 1:
                longest = self._longest(string, i, i+1)
                if len(longest) > len(longest_substring):
                    longest_substring = longest
        return longest_substring
    
    def _longest(self, string, start, end):
        longest = string[start]
        while 0 <= start <= end < len(string) and string[start] == string[end]:
            longest = string[start:end+1]
            start -= 1
            end += 1
        return longest

# Code (C++)

Approach 1:

// Longest Common Substring and then check the substring's indices.
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        string r = s; // The reverse of s.
        for (int i = 0; i < n/2; ++i)
        {
            std::swap(r[i], r[n-i-1]);
        }
        // maxCommonSubstringSize[x][y] is the longest common
        // substring size between s and r ending in s[x-1] and r[y-1].
        int maxCommonSubstringSize[n+1][n+1];
        for (int i = 0; i <= n; ++i)
        {
            maxCommonSubstringSize[0][i] = 0;
            maxCommonSubstringSize[i][0] = 0;
        }
        string res = "";
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                maxCommonSubstringSize[i][j] = 0;
                if (s[i-1] == r[j-1])
                {
                    maxCommonSubstringSize[i][j] =
                        maxCommonSubstringSize[i-1][j-1] + 1;
                }
                if (maxCommonSubstringSize[i][j] > res.size() &&
                    maxCommonSubstringSize[i][j] + n == i + j)
                    // The second condition is for the case like "aacdefcaa".
                    // The correct components for comparison are
                    // s[x−a[x][y]]⋯s[x−1] and r[y−a[x][y]]⋯r[y−1], where
                    // (x−a[x][y])+(y−1) = (x−1)+(y−a[x][y]) = n−1, that is
                    // x+y = a[x][y]+n
                {
                    res = s.substr(
                        (i - 1) - maxCommonSubstringSize[i][j] + 1,
                        maxCommonSubstringSize[i][j]);
                }
            }
        }
        return res;
    }
};
// Longest Common Substring and then check the substring's indices.
// Space optimization with a one-dementional array.
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        string r = s; // The reverse of s.
        for (int i = 0; i < n/2; ++i)
        {
            std::swap(r[i], r[n-i-1]);
        }
        // maxCommonSubstringSize[x] is the longest common
        // substring size between s and r ending in s[x-1] and r[y-1].
        int maxCommonSubstringSize[n+1];
        for (int i = 0; i <= n; ++i)
        {
            maxCommonSubstringSize[i] = 0;
        }
        string res = "";
        for (int i = 1; i <= n; ++i)
        {
            for (int j = n; j >= 1; --j)
            {
                maxCommonSubstringSize[j] = 0;
                if (s[i-1] == r[j-1])
                {
                    maxCommonSubstringSize[j] =
                        maxCommonSubstringSize[j-1] + 1;
                }
                if (maxCommonSubstringSize[j] > res.size() &&
                    maxCommonSubstringSize[j] + n == i + j)
                    // The second condition is for the case like "aacdefcaa".
                {
                    res = s.substr(
                        (i - 1) - maxCommonSubstringSize[j] + 1,
                        maxCommonSubstringSize[j]);
                }
            }
        }
        return res;
    }
};

Approach 2:

// Starting from both the head and tail of the array, we compare each pair of characters towards each other.
// Time Limit Exceeded.
class Solution {
private:
    bool isPalindrome(string s, int head, int tail)
    {
        while (head < tail)
        {
            if (s[head] != s[tail])
                return false;
            head++;
            tail--;
        }
        return true;
    }
public:
    string longestPalindrome(string s) {
        int n = s.size();
        string maxStr = "";
        for (int i = 0; i < n; ++i)
        {
            for (int j = i; j < n; ++j)
            {
                if (isPalindrome(s, i, j) && (j-i+1) > maxStr.size())
                    maxStr = s.substr(i, j-i+1);
            }
        }
        return maxStr;
    }
};

Approach 3:

// Starting from the middle of the array, we compare each pair of characters towards the reversed directions.
class Solution {
private:
    int longestPalindromeSize(string s, int head, int tail)
    {
        while (head >= 0 && tail < s.size())
        {
            if (s[head] != s[tail])
                break;
            head--;
            tail++;
        }
        return (tail-1) - (head+1) + 1;
    }
public:
    string longestPalindrome(string s) {
        string maxStr = "";
        for (int i = 0; i < s.size(); ++i)
        {
            int len = longestPalindromeSize(s, i, i);
            if (len > maxStr.size())
            {
                maxStr = s.substr(i-len/2, len);
            }
            len = longestPalindromeSize(s, i, i + 1);
            if (len > maxStr.size())
            {
                maxStr = s.substr(i-len/2+1, len);
            }
        }
        return maxStr;
    }
};

Approach 4:

// DP.
class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() == 0) return s;
        string maxStr = s.substr(0, 1);
        bool maxLen[s.size()][s.size() + 1];
        for (int head = 0; head < s.size(); ++head)
        {
            maxLen[head][0] = true;
            maxLen[head][1] = true;
        }
        for (int len = 2; len <= s.size(); ++len)
        {
            for (int head = 0; head < s.size(); ++head)
            {
                int tail = head + len - 1;
                if (tail >= s.size())
                    break;
                maxLen[head][len] = (s[head] == s[tail]) ? maxLen[head+1][len-2] : false;
                if (maxLen[head][len] && len > maxStr.size())
                    maxStr = s.substr(head, len);
            }
        }
        return maxStr;
    }
};