5 Longest Palindrome 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.

Solution 1: Create a table. O(n^2), O(n^2)

class Solution {
public:
    string longestPalindrome(string s) {
        int max_len = 0;
        string res;
        bool matrix[s.size()][s.size()];//Vector can't pass large test case
        for (int j=0;j<s.size();j++)
        {
            for (int i=0;i<=j;i++)
            {
                if (s[i]==s[j]&& (i+1>=j-1 || matrix[i+1][j-1]))
                    matrix[i][j]=true;
                else
                    matrix[i][j]= false;
                if (matrix[i][j])
                {
                    int len = j-i+1;
                    if (len>max_len)
                    {
                        max_len = len;
                        res = s.substr(i,max_len);
                    }
                }
            }
        }
        return res;
    }
};

Solution 2: Enumerate all possible substring. O(kn), O(k), k is the size of longest palindrome

class Solution {
public:
    string longestPalindrome(string s) {
        int maxLength = 0;
        int length=0;
        string res;
        for (int i=0;i<s.size();i++){
            for (int l=i,r=i;l>=0 && r<s.size() && s[l]==s[r];l--,r++){
                length = r-l+1;
                if (length>maxLength){
                    maxLength = length;
                    res = s.substr(l,length);
                }
            }
            for (int l=i,r=i+1;l>=0 && r<s.size() && s[l]==s[r];l--,r++){
                length = r-l+1;
                if (length>maxLength){
                    maxLength = length;
                    res = s.substr(l,length);
                }
            }
        }
        return res;
        
    }
};