loading

516. Longest Palindromic Subsequence — Step-by-Step Visualization

mediumLeetCode #516StringDynamic Programming

Given a string `s`, find the longest subsequence of `s` that is a palindrome. Return its length. A **subsequence** does not need to be contiguous. **Example 1:** Input: `s = "bbbab"` Output: `4` Explanation: One possible LPS is `"bbbb"`. **Example 2:** Input: `s = "cbbd"` Output: `2` Explanation: One possible LPS is `"bb"`.

Algorithm Pattern

Interval DP

Key Idea

dp[i][j] = length of longest palindromic subsequence in s[i..j]. Fill by increasing substring length. If s[i] == s[j], take dp[i+1][j-1] + 2; otherwise max(dp[i+1][j], dp[i][j-1]).

Step-by-Step Approach

  1. Initialize dp[i][i] = 1 for all i (every single char is a palindrome).
  2. For length 2 to n, for each starting index i (j = i + length - 1):
  3. If s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2.
  4. Else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
  5. Answer is dp[0][n-1].

Common Gotchas

  • dp[i+1][j-1] when length = 2: indices cross (i+1 > j-1). This gives dp[i][j] = 0 + 2 = 2 if chars match — correct.
  • Fill by length, not by row — ensures dp[i+1][...] and dp[...][j-1] are already computed.

Related Problems

← All problems