algoadvance

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.

Strategy

To solve this problem, we can use Dynamic Programming (DP).

1. Define the Subproblem:
   • Let dp[i][j] represent the length of the longest palindromic subsequence in the substring s[i...j].
2. Base Case:
   • When i == j, we only have one character, which is a palindrome of length 1. So, dp[i][j] = 1.
3. State Transition:
   • If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2 because the outer characters s[i] and s[j] contribute to the palindromic subsequence.
   • If s[i] != s[j], then dp[i][j] = max(dp[i+1][j], dp[i][j-1]) because we either exclude s[i] or s[j].
4. Initialization and Iteration:
   • We need to initialize the DP table for single character substrings (where i == j).
   • We then fill the table in a bottom-up manner by considering substrings of increasing lengths.
5. Result:
   • The length of the longest palindromic subsequence for the entire string s will be found at dp[0][n-1], where n is the length of s.

Code

Here’s the implementation in Python:

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    
    # Create a 2D DP array with all elements initialized to 0
    dp = [[0] * n for _ in range(n)]
    
    # Base case: Single letter sequences
    for i in range(n):
        dp[i][i] = 1
    
    # Fill the DP table
    for length in range(2, n + 1):  # length of the substring
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
    return dp[0][n - 1]

# Example usage
s = "bbbab"
print(longestPalindromeSubseq(s))  # Output: 4

Time Complexity

• Time Complexity: The time complexity is (O(n^2)) where (n) is the length of the string s. This is because we have two nested loops filling up the DP table, and each of the entries takes constant time to compute.

• Space Complexity: The space complexity is also (O(n^2)) due to the DP table.

This approach efficiently computes the length of the longest palindromic subsequence using dynamic programming.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?