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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Palindromic Subsequence

Difficulty: Medium

Problem Description

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.

Key Insights

  • A palindromic subsequence reads the same forwards and backwards.
  • We can use dynamic programming to build a solution by storing results of subproblems.
  • The length of the longest palindromic subsequence can be derived from considering characters at both ends of the string.

Space and Time Complexity

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

Solution

To solve the problem, we can use a dynamic programming approach. We create a 2D array dp where dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i:j+1]. The algorithm works as follows:

  1. Initialize dp[i][i] = 1 for all i, as every single character is a palindrome of length 1.
  2. Iterate over substring lengths from 2 to n.
  3. For each substring, check the characters at both ends:
    • If they are the same, dp[i][j] = dp[i+1][j-1] + 2.
    • If they are different, dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
  4. The answer will be found in dp[0][n-1], which represents the longest palindromic subsequence for the entire string.

Code Solutions

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    for i in range(n):
        dp[i][i] = 1  # Every single character is a palindrome

    for length in range(2, n + 1):  # length of 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]
← Back to All Questions