Leetcode Longest Palindromic Subsequence problem solution YASH PAL, 31 July 2024 In this Leetcode Longest Palindromic Subsequence problem solution Given a string s, find the longest palindromic subsequence’s length in s. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. Problem solution in Python. class Solution: def longestPalindromeSubseq(self, s): if not s: return 0 res = [[0 for i in range(len(s))] for i in range(len(s))] return self.helper(s, 0, len(s) - 1, res) def helper(self, inp, s, e, res): if s == e: return 1 if s > e: return 0 if res[s][e]: return res[s][e] if inp[s] == inp[e]: res[s][e] = 2 + self.helper(inp, s + 1, e - 1, res) else: res[s][e] = max(self.helper(inp, s + 1, e, res), self.helper(inp, s, e - 1, res)) return res[s][e] Problem solution in Java. class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); StringBuilder b = new StringBuilder(); b.append(s); b.reverse(); return solve(s, b.toString(), n, n); } int solve(String str1, String str2, int n, int m){ int[][] dp = new int[n + 1][m + 1]; //initialize for(int i = 0; i < n + 1; i++){ for(int j = 0; j < m + 1; j++){ if(i == 0 || j == 0) dp[i][j] = 0; } } //main code for(int i = 1; i < n + 1; i++){ for(int j = 1; j < m + 1; j++){ if(str1.charAt(i - 1) == str2.charAt(j - 1)){ dp[i][j] = 1 + dp[i - 1][j - 1]; }else{ dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]); } } } return dp[n][m]; } } Problem solution in C++. class Solution { public: int longestPalindromeSubseq(string s) { int n = s.size(); vector<vector<int>> dp(n+1,vector<int>(n+1,0)); for(int i=1;i<dp.size();i++) { for(int j=1;j<dp.size();j++) { if(s[i-1] == s[n-j]) { dp[i][j] = 1 + dp[i-1][j-1]; }else{ dp[i][j] = max(dp[i-1][j],dp[i][j-1]); } } } return dp[n][n]; } }; coding problems