516.Longest_Palindromic_Subsequence(Medium).md

516. Longest Palindromic Subsequence (Medium)

Date and Time: Dec 16, 2024, 22:57 (EST)

Link: https://leetcode.com/problems/longest-palindromic-subsequence

Question:

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.

Walk-through:

We can solve this question in the same way as 1143. Longest Common Subsequence.

We build a 2D DP table with s and s.reverse(), then we compare each char in s[r] and t[c], if they are the same, we update dp[r][c] = dp[r-1][c-1] + 1. Otherwise, dp[r][c] = max(dp[r-1][c], dp[r][c-1]).

2D DP Solution:

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        #     d b b c
        #   0 0 0 0 0
        # c 0 0 0 0 1
        # b 0 0 1 1 1
        # b 0 1 1 2 2
        # d 0 1 1 2 2

        # Build 2d DP table to find the longest common subsequence
        # Recurrence Relation: if s[r] == t[c]: dp[r][c] = 1 + dp[r-1][c-1]
        # If s[r] != t[c]: max(dp[r+1][c], dp[r][c-1])

        # TC: O(n^2), n = len(s), SC: O(n^2)
        dp = [[0] * (len(s)+1) for _ in range(len(s)+1)]
        t = s[::-1]
        for r in range(1, len(s)+1):
            for c in range(1, len(s)+1):
                if s[r-1] == t[c-1]:
                    dp[r][c] = dp[r-1][c-1] + 1
                else:
                    dp[r][c] = max(dp[r-1][c], dp[r][c-1])
        return dp[-1][-1]

Time Complexity: $O(n^2)$
Space Complexity: $O(n^2)$

1D DP Solution:

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        # Recurrence Relation: if s[r] == t[c]: dp[r][c] = dp[r-1][c-1] + 1
        # Else: dp[r][c] = max(dp[r-1][c], dp[r][c-1])

        # TC: O(n^2), n = len(s), SC: O(n)
        dp = [0] * (len(s) + 1)
        t = s[::-1]
        for r in range(1, len(s)+1):
            tmp = dp.copy()     # Save the copy of dp
            for c in range(1, len(s)+1):
                if s[r-1] == t[c-1]:
                    dp[c] = tmp[c-1] + 1
                else:
                    dp[c] = max(tmp[c], dp[c-1])
        return dp[-1]

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$