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.
Example 1:
Input: s = "bbbab" Output: 4 Explanation: One possible longest palindromic subsequence is "bbbb". Solution:
Memoization approch:
Time complexity : o(n*m) and space complexity : o(n*m) + o(n) (o(n) is extra stack space utilized)
//intuition /* normal or brute force way: generate all possible subsequences and find the largest subsequence that is palindrome; optimal approach : Using Logic of longest common subsequence; example : if s = bbbab, lets reverse it as r = babbb now the we can perform longest common subsequence to get result as 3 (bbb) and that will be the required result; */ class Solution { public int longestPalindromeSubseq(String s) { //bottom up approach StringBuilder sb = new StringBuilder(); sb.append(s); String r= sb.reverse().toString(); int dp[][] = new int[s.length()][r.length()]; for(int row[]: dp){ Arrays.fill(row,-1); } return longestPalindromicSubsequence(s.length()-1,r.length()-1,s,r,dp); } //Memoization approach public int longestPalindromicSubsequence(int i,int j, String a, String b,int dp[][]){ if(i<0 || j<0){ return 0; } if(dp[i][j]!=-1) return dp[i][j]; if(a.charAt(i)==b.charAt(j)){ return dp[i][j] = 1 + longestPalindromicSubsequence(i-1,j-1,a,b,dp); } return dp[i][j]= 0 + Integer.max(longestPalindromicSubsequence(i,j-1,a,b,dp), longestPalindromicSubsequence(i-1,j,a,b,dp)); } } Tabulation Approach:
Time complexity : o(n*m) and space complexity : o(n*m)
class Solution { public int longestPalindromeSubseq(String s) { //bottom up approach StringBuilder sb = new StringBuilder(); sb.append(s); String r= sb.reverse().toString(); int dp[][] = new int[s.length()+1][r.length()+1]; //base case //its 1 base indexing //lets put first row and first column as 0 for(int i = 0;i<=s.length();i++){ dp[i][0] = 0; dp[0][i] = 0; } for(int i =1;i<=s.length();i++){ for(int j =1;j<=r.length();j++){ if(s.charAt(i-1)==r.charAt(j-1)){ dp[i][j] = 1 + dp[i-1][j-1]; } else dp[i][j] = 0 + Integer.max(dp[i][j-1],dp[i-1][j]); } } return dp[s.length()][r.length()]; } } 
Top comments (0)