<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:
    // vector<string> ans;

    bool isPalin(string s) {

        int n = s.size();
        int i = 0, j = n - 1;

        while (i <= j) {
            if (s[i] != s[j])
                return false;
            i++;
            j--;
        }

        return true;
    }

    // void solve(int i, int j, string s) {
    //     int n = s.size();
    //     int i = 0, j = n - 1;
    //     while (i <= j) {

    //         if (isPalin())
    //     }
    // }
    string longestPalindrome(string s) {

        int n = s.size();
        int len = 0;
        string ans = "";

        int dp[1005][1005];
        memset(dp, -1, sizeof(dp));

        for (int i = 0; i < n; i++) {
            string str = "";
            // str+=s[i];
            // if (isPalin(str) && str.size() > len) {
            //     len = str.size();
            //     ans = str;
            // }
            for (int j = i; j < n; j++) {

                str += s[j];
                // if (isPalin(str) && str.size() > len) {
                //     len = str.size();
                //     ans = str;
                // }
                if (dp[i][j] == 0)
                    continue;
                if (dp[i][j] != -1 && dp[i][j] == 1) {

                    if (str.size() > len) {
                        len = str.size();
                        ans = str;
                    }
                } else {

                    int a = i;
                    int b = j;
                    bool f = true;

                    while (a <= b) {

                        if (dp[a][b] == -1) {
                            if (s[a] == s[b]) {
                                a++;
                                b--;
                            } else {
                                f = false;
                                break;
                            }
                        } else if (dp[a][b] == 1)
                            break;
                        else if (dp[a][b] == 0) {
                            f = false;
                            break;
                        }
                    }
                    if (f) {
                        dp[i][j] = 1;
                        if (str.size() > len) {
                            len = str.size();
                            ans = str;
                        }
                    } else
                        dp[i][j] = 0;
                }
            }
        }

        return ans;
    }
};
131948