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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Longest Palindromic Subsequence and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →