class Solution {
public:
    bool cheak(string &s , int left ,int right)
    {
        for(int i = left , j = right ; i<j ; i++ , j--)
        {
            if(s[i] != s[j]) return false;
        }
        return true;
    }
    string longestPalindrome(string s) {
        if(s.size() <= 1) return s;
        int string_max = 0;
        string result;
        for(int i=0 ; i<s.size() ;i++)
        {
            for(int j=i ; j<s.size() ;j++)
            {
                if(s[j] == s[i] && cheak(s,i,j) == true && (j-i+1) > string_max)
                {
                    // cout<<i<<' '<<j<<endl;
                    string_max = j-i+1;
                    result.assign(s.begin()+i , s.begin()+j+1);
                } 
            }   
        }
        return result;
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() <= 1) return s;
        vector<vector<bool>> dp(s.size() , vector<bool>(s.size() , false));
        int left = 0 , right = 0;
        for(int i=s.size()-1 ; i>=0 ; i--)
        {
            for(int j=i ; j<s.size() ;j++)
            {
                if(s[i] == s[j] && (j-i<=1 ||dp[i+1][j-1] == true) ) 
                {
                    dp[i][j] = true;
                    if( j-i > right -left) 
                    {
                        left = i;
                        right = j;
                    }
                }
            }
        }
        string result(s.begin()+left , s.begin()+right+1);
        return result;
    }
};

class Solution {
public:
    bool cheak(string &s , int left , int right)
    {
        for(int i=left , j=right ; i<j ; i++ ,j--)
        {
            if(s[i] != s[j]) return false;
        }
        return true;
    }
    string longestPalindrome(string s) {
        string result;
        for(int i=0 ; i<s.size() ;i++)
        {
            for(int j=i ; j<s.size() ;j++)
            {
                if(s[i] == s[j] && cheak(s,i,j) == true && (j-i+1) > result.size())
                {
                    string tmp(s.begin()+i , s.begin()+j+1);
                    result = tmp;
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>> dp(s.size() , vector<bool>(s.size(),false));
        int left = 0 , right = 0;
        for(int i=s.size()-1 ; i>=0 ;i--)
        {
            for(int j=i ; j<s.size() ;j++)
            {
                if(s[i] == s[j] && ( j-i<=1 || dp[i+1][j-1] == true ))
                {
                    dp[i][j] = true;
                    if(j-i > right-left)
                    {
                        left = i;
                        right = j;
                    }
                }
            }
        }
        return string(s.begin()+left , s.begin()+right+1);
    }
};