<p>Given a string <code>s</code>, return <em>the longest</em> <span data-keyword="palindromic-string"><em>palindromic</em></span> <span data-keyword="substring-nonempty"><em>substring</em></span> in <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;babad&quot;
<strong>Output:</strong> &quot;bab&quot;
<strong>Explanation:</strong> &quot;aba&quot; is also a valid answer.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cbbd&quot;
<strong>Output:</strong> &quot;bb&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consist of only digits and English letters.</li>
</ul>

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                int l = i + j;
                if(l < n){
                    //dp[l][j]
                    if(l == j){
                        dp[j][l] = 1;
                    }else{
                        if(l - j == 1){
                            if(s[l] == s[j]){
                                dp[j][l] = 2;
                            } 
                            continue;
                        }
                        if(s[l] == s[j] && dp[j + 1][l - 1] != 0){
                            dp[j][l] = dp[j + 1][l - 1] + 2;
                        }
                        
                    }
                }else
                break;
            }
        }
        int p, q;
        int val = INT_MIN;
        for(int i = 0; i< n; i++){
            for(int j = 0; j < n; j++){
                // cout << dp[i][j] << " ";
                if(val < dp[i][j]){
                    val = dp[i][j];
                    p = i;
                    q = j;
                }
            }
            cout << endl;
        }
        string ans = "";
        // cout << p << " " << q << endl;
        for(int i = p; i <= q; i++){
            ans = ans + s[i];
        }
        return ans;
    }
};
//     0 1 2 3 4
//     b a b a d
// 0 b 1 0 
// 1 a   1 0
// 2 b     1 0
// 3 a       1 0
// 4 d         1 
313335