Longest Palindromic Subsequence - Amazon Top Interview Questions

                        Solution in C++ :

int dp[3][1005];
int solve(string s) {
    memset(dp[0], 0, sizeof(dp[0]));
    for (int i = 0; i < s.size(); i++) {
        dp[1][i] = 1;
    }
    for (int a = 2; a <= s.size(); a++) {
        memset(dp[2], -1, sizeof(dp[2]));
        for (int i = 0; i + a <= s.size(); i++) {
            int j = i + a - 1;
            if (s[i] == s[j]) dp[2][i] = max(dp[2][i], 2 + dp[0][i + 1]);
            dp[2][i] = max(dp[2][i], max(dp[1][i], dp[1][i + 1]));
        }
        memcpy(dp[0], dp[1], sizeof(dp[0]));
        memcpy(dp[1], dp[2], sizeof(dp[0]));
    }
    return dp[1][0];
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(String s) {
        int n = s.length();
        if (n <= 1)
            return n;
        int[][] dp = new int[n][n];
        int res = 1;

        for (int i = 0; i < n; i++) dp[i][i] = 1;

        for (int LENGTH = 2; LENGTH <= n; LENGTH++) {
            for (int i = 0; i < n; i++) {
                if (i + LENGTH - 1 >= n)
                    break;
                int cand = Math.max(dp[i + 1][i + LENGTH - 1], dp[i][i + LENGTH - 2]);
                if (s.charAt(i) == s.charAt(i + LENGTH - 1)) {
                    cand = Math.max(cand, 2 + dp[i + 1][i + LENGTH - 2]);
                }
                dp[i][i + LENGTH - 1] = cand;
            }
        }
        return dp[0][n - 1];
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, s):

        n = len(s)

        @functools.lru_cache(None)
        def dp(i, j):
            if i == j:
                return 1
            elif i > j:
                return 0
            else:
                if s[i] == s[j]:
                    return 2 + dp(i + 1, j - 1)
                else:
                    return max(dp(i + 1, j), dp(i, j - 1))

        return dp(0, n - 1)