Longest Palindromic Subsequence

Problem

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. (link)

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Constraints:

• 1 <= s.length <= 1000

• s consists only of lowercase English letters.

Solution

• To find the longest palindromic subsequence, we can use the concept of the longest common subsequence between two strings.

• Here, the two strings are the original string and its reverse.

• By comparing the original string with its reversed version, any common matches represent palindromic subsequences.

• If a string is the same when reversed, it is a palindrome.

• Therefore, comparing the string with its reverse helps identify the longest palindromic subsequence.

Time - O(mxn)

Space - O(mxn) + O(m+n)→ stack space

class Solution {

    private int lcs(int i, int j, String text1, String text2, int[][] dp){

        if(i<0 || j<0) return 0;

        if(dp[i][j]!=-1) return dp[i][j];

        if(text1.charAt(i) == text2.charAt(j)){
            return dp[i][j] = 1 + lcs(i-1, j-1, text1, text2, dp);
        }

        return dp[i][j] = Math.max(lcs(i-1, j, text1, text2, dp), lcs(i, j-1, text1, text2, dp));
    }


    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for(int[] row : dp){
            Arrays.fill(row, -1);
        }
        String reversed = new StringBuilder(s).reverse().toString();
        return lcs(n-1, n-1, s, reversed, dp);
    }
}