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

    int& getBool(vector<int>& mat, int row,int col, int len){
        return mat[col+row*len];
    }


    string longestPalindrome(string s) {
        int len = s.size();
        int max = -1;
        string longest;
        //satrt index=row, end index = col
        vector<int> mat(pow(len,2),0);
        for(int j = 0; j < s.size(); j++){
            mat[j+j*s.size()]=1;
        }
        for(int j = 0; j < s.size()-1; j=j+2){
            if(s[j]==s[j+1]){
                mat[(j+1)+j*s.size()]=1;
            }
        }
        for(int i = 0; i<s.size(); i++){
            for(int j = 0; j < s.size()-i; j+=(i+1)){
                if(s[j]==s[j+i]&&(getBool(mat,j+1,j+i-1,len))){
                    getBool(mat,j,j+i,len)=1;
                    if(i>max){
                        max = i;
                        longest=s.substr(j, i);
                    }
                }
            }
        }
        return longest;
    }
};
*/

class Solution {
public:
    int& getBool(vector<int>& mat, int row, int col, int len) {
        return mat[col + row * len];
    }

    string longestPalindrome(string s) {
        int len = s.size();
        int max_len = -1;
        string longest;

        // Initialize the matrix with size len * len
        vector<int> mat(len * len, 0);

        // Every single character is a palindrome
        for (int j = 0; j < len; j++) {
            mat[j + j * len] = 1;
        }

        // Check for palindromes of length 2
        for (int j = 0; j < len - 1; j++) {
            if (s[j] == s[j + 1]) {
                mat[(j + 1) + j * len] = 1;
                if (2 > max_len) {
                    max_len = 2;
                    longest = s.substr(j, 2);
                }
            }
        }

        // Check for palindromes of length greater than 2
        for (int i = 2; i < len; i++) {
            for (int j = 0; j + i < len; j++) {
                if (s[j] == s[j + i] && getBool(mat, j + 1, j + i - 1, len)) {
                    getBool(mat, j, j + i, len) = 1;
                    if (i + 1 > max_len) {
                        max_len = i + 1;
                        longest = s.substr(j, i + 1);
                    }
                }
            }
        }
        return longest.empty() ? s.substr(0, 1) : longest;
    }
};
264965