<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 length = s.length();

        if (length == 0)
            return "";

        int maxl = 1; // Length of the longest palindrome
        int start = 0; // Starting index of the longest palindrome

        // Allocate memory for the DP matrix and initialize it to 0
        int *matrix = new int[length * length]{0};

        // Single character palindromes
        for (int i = 0; i < length; i++) {
            matrix[i * length + i] = 1;
        }

        for (int i = length - 1; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                if (s[i] == s[j]) {
                    if (j - i == 1 || matrix[(i + 1) * length + (j - 1)] == 1) {
                        matrix[i * length + j] = 1;
                        if (j - i + 1 > maxl) {
                            maxl = j - i + 1;
                            start = i;
                        }
                    }
                }
            }
        }

        delete[] matrix; // Don't forget to free the allocated memory
        return s.substr(start, maxl);
    }

};
252873