https://leetcode.com/problems/longest-palindromic-substring/

Solution

Dynamic programming:

bool fx[i][j] = true if s[i..j] is palindromic else false
fx[i][i] = true
fx[i][i+1] = (s[i] == s[i+1])
fx[i][j] = (s[i] == s[j] && fx[i+1][j-1])

result = max(j-i+1) if fx[i][j]

    string longestPalindrome(string s) {
        int n = s.length();
        if (n == 0) return "";
        
        int u = 0, v = 0;
        int maxLen = 1;
        
        bool fx[n][n];
        memset(fx, false, sizeof(fx));
        
        for(int i = 0; i < n; i++) {
            fx[i][i] = 1;
            if (i < n-1 && s[i] == s[i+1]){
                fx[i][i+1] = 1;
                maxLen = 2;
                u = i;
                v = i + 1;
            }
        }
        
        for(int len = 3; len <= n; len++) {
            for(int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                fx[i][j] = s[i] == s[j] ? fx[i+1][j-1] : 0;
                if (fx[i][j]) {
                    maxLen = len;
                    u = i;
                    v = j;
                }
            }
        }
        
        return s.substr(u, v-u+1);
    }

Runtime: O(n^2)

One possible mistake in this solution's impl is we forgot the initilize maxLen when considering base cases (fx[i][i], fx[i][i+1])