<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:

        bool solve(int i, int j, string &s, int n, vector<vector<int>>&dp)
        {

            if (i == n || j < 0) return 0;

            
            if(dp[i][j] != -1)
                return dp[i][j];
            if (i >= j)
                return true;
        
            if (s[i] == s[j])
            {
                return dp[i][j] =  solve(i + 1, j - 1, s, n, dp);
            }

            return dp[i][j] =  false;
        }
    string longestPalindrome(string s)
    {

        int n = s.size();
        vector<vector<int>>dp(n, vector<int>(n, -1));
        int maxSize = INT_MIN;
        string ans;
        int startIndex;
        for (int i = 0; i < n; i++)
        {
            string temp = "";

            for (int j = i; j < n; j++)
            {
                temp += s[j];

                if (solve(i, j, s, n, dp))
                {
                    if (j - i + 1 > maxSize)
                    {
                        maxSize = j - i + 1;
                        startIndex = i;
                    }   
                }
            }
        }

        return s.substr(startIndex, maxSize);
    }
};
385890