Skip to main content

516. Longest Palindromic Subsequence

medium

Find the length of the longest subsequence of s that is also a palindrome. Classic interval DP: dp[i][j] = length of the longest palindromic subsequence inside s[i..j], filled in increasing-length order.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= s.length <= 1000
  • s consists only of lowercase English letters.

Examples

Example 1

Input
s = "bbbab"
Output
4

Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2

Input
s = "cbbd"
Output
2

Explanation: One possible longest palindromic subsequence is "bb".

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Interval DP. dp[i][j] = length of the longest palindromic subsequence in s[i..j].

Hint 2

If s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2.

Hint 3

Else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

Hint 4

Fill in increasing interval length so dp[i+1][j-1] is ready when needed. Base: dp[i][i] = 1.

Solution approach

Reveal approach

Bottom-up interval DP. dp[i][j] is the length of the longest palindromic subsequence in s[i..j]. Initialize the diagonal dp[i][i] = 1 (a single char is its own length-1 palindrome). Iterate length = 2..n and i = 0..n-length, set j = i + length - 1. If s[i] == s[j], dp[i][j] = dp[i+1][j-1] + 2 (with the convention dp[i+1][i] = 0 for length 2). Otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Return dp[0][n-1]. Alternative framing: this equals LCS(s, reverse(s)) — same answer, same complexity, often easier to reason about for students who already know LCS.

Complexity

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

Related patterns

  • dynamic-programming
  • interval-dp
  • string-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Uber

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →