LeetCode 516 - Longest Palindromic Subsequence

The problem asks us to determine the length of the longest palindromic subsequence within a given string s. A palindromic subsequence is a sequence of characters that reads the same forwards and backwards and can be obtained by deleting zero or more characters from the…

leetcodemediumstringdynamic-programming

LeetCode Problem 516

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to determine the length of the longest palindromic subsequence within a given string s. A palindromic subsequence is a sequence of characters that reads the same forwards and backwards and can be obtained by deleting zero or more characters from the original string without changing the order of the remaining characters.

For instance, in the string "bbbab", the longest palindromic subsequence is "bbbb", which has a length of 4. Similarly, in "cbbd", the longest palindromic subsequence is "bb" with a length of 2.

The input is a string s containing only lowercase English letters, with a length between 1 and 1000. This constraint is important because it suggests that a brute-force approach that generates all subsequences would be computationally infeasible due to exponential time complexity.

Key edge cases include strings that are already palindromes, strings where all characters are distinct, or strings of length 1. The problem guarantees that the input will always be valid, so there are no empty strings or invalid characters to handle.

Approaches

A brute-force approach would involve generating all possible subsequences of s and checking whether each one is a palindrome. The longest palindrome found would then be returned. This approach is correct because it exhaustively considers all possibilities, but it is extremely inefficient. Generating all subsequences has a time complexity of O(2^n), which is impractical for n up to 1000.

The optimal approach leverages dynamic programming. The key insight is that the problem has overlapping subproblems and optimal substructure. If we define dp[i][j] as the length of the longest palindromic subsequence in the substring s[i:j+1], we can build solutions for larger substrings from smaller ones. Specifically, if s[i] == s[j], the endpoints contribute to the palindrome length, and we add 2 to the length of the subsequence in s[i+1:j]. Otherwise, the result is the maximum between the subsequences obtained by excluding either end.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Generate all subsequences and check palindromes
Optimal O(n^2) O(n^2) Dynamic programming using a 2D table to store intermediate results

Algorithm Walkthrough

  1. Initialize a 2D array dp of size n x n where n is the length of s. Each entry dp[i][j] will store the length of the longest palindromic subsequence in the substring s[i:j+1].
  2. Set all diagonal entries dp[i][i] to 1 since a single character is a palindrome of length 1.
  3. Iterate over all possible substring lengths starting from 2 up to n. For each length, iterate over the starting index i and compute the ending index j = i + length - 1.
  4. If s[i] == s[j], set dp[i][j] = dp[i+1][j-1] + 2 since the two matching characters extend the inner palindrome.
  5. If s[i] != s[j], set dp[i][j] = max(dp[i+1][j], dp[i][j-1]) since one of the endpoints must be excluded.
  6. Return dp[0][n-1], which represents the length of the longest palindromic subsequence for the entire string.

Why it works: The algorithm maintains the invariant that dp[i][j] always represents the length of the longest palindromic subsequence for the substring s[i:j+1]. By filling the table from shorter substrings to longer ones, each computation relies only on already computed values, ensuring correctness.

Python Solution

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        
        for i in range(n):
            dp[i][i] = 1
        
        for length in range(2, n + 1):
            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]

The code first initializes a 2D table for dynamic programming. Single-character substrings are set to length 1. For all other substrings, it checks if the endpoints match. If they do, it extends the inner palindrome by 2; otherwise, it selects the maximum subsequence length by excluding either endpoint. Finally, it returns the value for the entire string.

Go Solution

func longestPalindromeSubseq(s string) int {
    n := len(s)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    }
    
    for length := 2; length <= n; length++ {
        for i := 0; i <= n - length; i++ {
            j := i + length - 1
            if s[i] == s[j] {
                if length == 2 {
                    dp[i][j] = 2
                } else {
                    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]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

In Go, slices are used to create the 2D dynamic programming table. Special handling is added for substrings of length 2 to prevent indexing errors. The rest of the algorithm mirrors the Python solution, computing the longest palindromic subsequence iteratively.

Worked Examples

Example 1: "bbbab"

i j dp[i][j] Explanation
0 0 1 Single character 'b'
1 1 1 Single character 'b'
0 1 2 'bb' is a palindrome
0 4 4 'bbbb' is longest palindromic subsequence

Example 2: "cbbd"

i j dp[i][j] Explanation
0 0 1 'c'
1 2 2 'bb'
0 3 2 Maximum between 'cbb' and 'bbd'

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) We compute dp[i][j] for each pair i, j, and each computation is O(1)
Space O(n^2) We store the DP table of size n x n

Dynamic programming reduces the exponential brute-force time complexity to polynomial O(n^2), which is feasible for n up to 1000.

Test Cases

# Provided examples
assert Solution().longestPalindromeSubseq("bbbab") == 4  # multiple 'b's form "bbbb"
assert Solution().longestPalindromeSubseq("cbbd") == 2   # "bb"

# Edge and boundary cases
assert Solution().longestPalindromeSubseq("a") == 1       # single character
assert Solution().longestPalindromeSubseq("abcd") == 1    # all distinct characters
assert Solution().longestPalindromeSubseq("aaa") == 3     # all same characters
assert Solution().longestPalindromeSubseq("abacdfgdcaba") == 7  # "aba" + "cdc" + "aba" (longest palindrome subsequence)
Test Why
"bbbab" Tests multiple repeating characters
"cbbd" Tests simple two-character palindrome
"a" Tests minimal input
"abcd" Tests no repeating characters
"aaa" Tests all identical characters
"abacdfgdcaba" Tests longer string with embedded palindromes

Edge Cases

Single-character string: The function correctly returns 1, because a single character is always a palindrome.

All distinct characters: When no two characters are the same, the longest palindromic subsequence is 1. The DP solution handles this naturally by taking the max between dp[i+1][j] and dp[i][j-1].

String with repeated palindromes in the middle: Strings like "abacdfgdcaba" require the algorithm to consider multiple overlapping palindromic subsequences. The DP approach correctly accumulates the lengths of inner palindromes, ensuring the global maximum is computed.