We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Palindromic Subsequence

Number: 516

Difficulty: Medium

Paid? No

Companies: LinkedIn, Meta, Amazon, Google, Cisco, Uber

Problem Description

Given a string s, determine the length of its longest palindromic subsequence. A subsequence is a sequence derived from the string by deleting some or no characters while keeping the original order.

Key Insights

  • The problem can be solved efficiently using dynamic programming.
  • A 2D DP table is used where dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i...j].
  • If the characters at the two ends of the substring match (s[i] == s[j]), they contribute to the palindrome length.
  • Otherwise, the solution is the maximum sequence length by either excluding the left or the right character.
  • The approach builds the solution from smaller substrings (length 1) to the entire string.

Space and Time Complexity

Time Complexity: O(n^2) where n is the length of the string. Space Complexity: O(n^2) due to the usage of a 2D DP table.

Solution

We solve this problem using a bottom-up dynamic programming approach. We create a 2D table dp[][] such that dp[i][j] stores the longest palindromic subsequence length for the substring s[i...j]. For any single character, dp[i][i] is 1. For substrings of length greater than 1, if the characters at positions i and j (s[i] and s[j]) match, then dp[i][j] = dp[i+1][j-1] + 2. If they do not match, we take the maximum of dp[i+1][j] and dp[i][j-1]. Finally, the dp[0][n-1] holds the result for the entire string.

Code Solutions

# Function to compute the longest palindromic subsequence length
def longest_palindromic_subseq(s):
    n = len(s)
    # Create a 2D DP table initialized to 0
    dp = [[0] * n for _ in range(n)]
    
    # Base case: every single character is a palindrome of length 1
    for i in range(n):
        dp[i][i] = 1
    
    # Build the table. 'sub_len' is the current length of substring we are considering.
    for sub_len in range(2, n+1):
        for i in range(n - sub_len + 1):
            j = i + sub_len - 1  # Compute the end index of the substring
            if s[i] == s[j]:
                # Characters match, add 2 to the result from the inner substring if available
                dp[i][j] = 2 + (dp[i+1][j-1] if sub_len > 2 else 0)
            else:
                # Characters don't match, choose the maximum from either excluding left or right char
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    # The answer for the full string is stored at dp[0][n-1]
    return dp[0][n-1]

# Example usage:
s = "bbbab"
print(longest_palindromic_subseq(s))  # Expected output: 4
← Back to All Questions