516. Longest Palindromic Subsequence
Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 55.8%
Problem Breakdown
We are given a string s containing lowercase English letters. We need to find the length of the longest subsequence that is also a palindrome (reads the same forwards and backwards).
Key distinctions here:
- Subsequence vs Substring: Characters do not need to be contiguous; we can skip characters, but their relative order must remain unchanged.
- Palindrome Property: The first character chosen from the left must match some character on the right side of that range for them to contribute to a palindrome pair.
Constraints: s length is between 1 and 1000. This suggests an solution is acceptable (since operations), but we must avoid exponential solutions like brute-force recursion without memoization ().
Intuition
A naive approach would be to generate every possible subsequence and check if it’s a palindrome. There are subsequences for length N, making this infeasible for large inputs (Time Complexity: or worse).
We recognize that the Longest Palindromic Subsequence problem is structurally similar to finding the Longest Common Subsequence (LCS) between a string and its reverse. However, we can solve this more directly using Dynamic Programming without explicitly constructing the reversed string logic which might confuse indices.
The core insight for DP:
Consider a substring s[i...j].
- If characters at both ends match (
s[i] == s[j]), they contribute to the palindrome length (2) plus whatever is inside them (dp[i+1][j-1]). - If they don’t match, we cannot use both. We must discard either
s[i]ors[j], so we take the maximum of solving fors[i+1...j]ands[i...j-1].
This suggests a 2D DP table where state (i, j) represents the LPS length in substring from index i to j. We build this bottom-up starting from substrings of length 1 up to N.
Approach
We will use an iterative Dynamic Programming approach with a 2D array dp[i][j], representing the length of the longest palindromic subsequence within s[i...j] inclusive.
Initialization:
- Every single character is a palindrome of length 1, so we initialize diagonal elements where
i == j. - We iterate through all possible substring lengths from 2 to N (or gap size).
Transitions:
For each pair (i, j) with :
- If
s[i] == s[j]:- The characters match and can be part of the palindrome. Add 2 to the result of the inner substring:
dp[i][j] = dp[i+1][j-1] + 2.
- The characters match and can be part of the palindrome. Add 2 to the result of the inner substring:
- Else (
s[i] != s[j]):- We cannot include both ends simultaneously in a matching pair for this specific boundary. Take the best option from excluding either side:
dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
- We cannot include both ends simultaneously in a matching pair for this specific boundary. Take the best option from excluding either side:
Result:
The answer will be stored in dp[0][n-1], representing the LPS of the entire string.
Complexity Analysis
- Time Complexity: . We fill an table, and for each cell we perform constant time work (comparison and max). With , this is roughly 500k operations, well within limits.
- Space Complexity: to store the DP table. This can be optimized to by only keeping track of two rows or using a gap-based optimization (since
dp[i][j]depends on values from previous gaps), but for clarity and standard interview expectations, the 2D array is acceptable here given memory limits usually allow ~10MB+.
Solution
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
# dp[i][j] stores LPS length for substring s[i...j]
dp = [[0] * n for _ in range(n)]
# Base case: single characters are palindromes of length 1
for i in range(n):
dp[i][i] = 1
# Iterate over gap size (length - 1) from 1 to n-1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
# If characters match, add 2 and result from inner substring
dp[i][j] = dp[i+1][j-1] + 2
else:
# Otherwise take max of excluding left or right character
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n - 1]
Edge Cases Handled
- Single Character String: The loop for
lengthstarts at 2, so the base case initialization handles length 1 strings correctly (returns 1). - No Matching Characters (e.g., “abc”): The logic defaults to taking max of sub-parts. Since no matches occur beyond single chars, it returns 1.
- All Same Characters (e.g., “aaaaa”):
s[i] == s[j]always true for valid ranges, accumulating length correctly up to N. - Empty Input: Constraints state , but the code would return 0 if initialized with empty string logic implicitly handled by loops not executing (though constraints prevent this).