Longest palindromic substring. - Dynamic Programming O(n^2) time and O(n) space.

subsequence.cpp

int longestPalindromeSubsequence(string A) {
  
    int n = A.length();
    int dp[3][n];

    int res = 1;
    for (int l = 1; l <= n; l++) {
        int idx = (l - 1) % 3;
        for (int left = 1; left <= n - l + 1; left++) {
            int right = left + l - 1;

            if (l == 1)
                dp[idx][left] = 1;
            else if (l == 2)
                dp[idx][left] = 1 + (A[left - 1] == A[right - 1]);
            else if (A[left - 1] == A[right - 1])
                dp[idx][left] = dp[(idx + 1) % 3][left + 1] + 2;
            else
                dp[idx][left] = max(dp[(idx + 2) % 3][left], dp[(idx + 2) % 3][left + 1]);

            res = max(res, dp[idx][left]);
        }
    }

    return res;
}

substring.cpp

void longestPalindromeSubstring(string A) {
    
    int n = A.length();
    int dp[3][n];

    auto res = make_pair(0, 1);
    for (int l = 1; l <= n; l++) {
        
        int idx = (l - 1) % 3;
        for (int left = 1; left <= n - l + 1; left++) {
            
            int right = left + l - 1;
            int pre = (idx + 1) % 3;

            if (l == 1)
                dp[idx][left] = 1;
            else if (l == 2)
                dp[idx][left] = A[left - 1] == A[right - 1];
            else
                dp[idx][left] = A[left - 1] == A[right - 1] && dp[pre][left + 1] == 1;
            
            if (dp[idx][left] && l > res.second)
                res = make_pair(left - 1, l);
        }
    }

    cout << A.substr(res.first, res.second) << "\n";
}