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 - 1D DP Bottom up

• Classic one backward then forward loop if we encounter similar then we add 2 because we need to include both i and j and for case it is not we need to check if we exclude i or j in between these two which is maximum
• O(n^2), O(n)

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[] dp = new int[n];
        Arrays.fill(dp,1);
 
        for (int i = n - 1; i >= 0; i--) {
            int p = 0;
            for (int j = i + 1; j < n; j++) {
                int tmp = dp[j];
                if (s.charAt(i) == s.charAt(j))
                    dp[j] = p + 2;
                else
                    dp[j] = Math.max(dp[j],dp[j-1]);
                p = tmp;
            }
        }
 
        return dp[n-1];
    }
}