Domain 2MediumCORE

Longest Palindromic Subsequence

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).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming

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:

  1. Subsequence vs Substring: Characters do not need to be contiguous; we can skip characters, but their relative order must remain unchanged.
  2. 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 O(N2)O(N^2) solution is acceptable (since 10002=1,000,0001000^2 = 1,000,000 operations), but we must avoid exponential solutions like brute-force recursion without memoization (O(2N)O(2^N)).

Intuition

A naive approach would be to generate every possible subsequence and check if it’s a palindrome. There are 2N−12^N - 1 subsequences for length N, making this infeasible for large inputs (Time Complexity: O(N⋅2N)O(N \cdot 2^N) 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] or s[j], so we take the maximum of solving for s[i+1...j] and s[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 j>ij > i:

  1. 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.
  2. 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]).

Result: The answer will be stored in dp[0][n-1], representing the LPS of the entire string.

Complexity Analysis

  • Time Complexity: O(N2)O(N^2). We fill an N×NN \times N table, and for each cell we perform constant time work (comparison and max). With N=1000N=1000, this is roughly 500k operations, well within limits.
  • Space Complexity: O(N2)O(N^2) to store the DP table. This can be optimized to O(N)O(N) 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 length starts 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 N≥1N \geq 1, but the code would return 0 if initialized with empty string logic implicitly handled by loops not executing (though constraints prevent this).