Longest Palindromic Subsequence

 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".

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.

Approach 1:

💡 Concept:

We reverse the string and apply the LCS concept:

• If s = "bbabcbcab", then:

• rev = "bacbcbabb"

• Find LCS(s, rev) → that will be the longest palindromic subsequence

• It look like Longest string subsequence question

class Solution {

    public int lcs(String s1, String s2, int i, int j, int[][] dp) {

        if (i == s1.length() || j == s2.length()) return 0;

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

        if (s1.charAt(i) == s2.charAt(j)) {

            dp[i][j] = 1 + lcs(s1, s2, i + 1, j + 1, dp);

        } else {

            dp[i][j] = Math.max(

                lcs(s1, s2, i + 1, j, dp),

                lcs(s1, s2, i, j + 1, dp)

            );

        }

        return dp[i][j];

    }

    public int longestPalindromeSubseq(String s) {

        String rev = new StringBuilder(s).reverse().toString();

        int n = s.length();

        int[][] dp = new int[n][n];

        for (int[] row : dp) {

            Arrays.fill(row, -1);

        }

        return lcs(s, rev, 0, 0, dp);

    }

}