516. Longest Palindromic Subsequence
Asked at Microsoft, Goldman Sachs
Difficulty
Medium
Time
O(n^2)
Space
O(n^2)
Pattern
String
Companies
2
Problem
You are given a string s. Find the length of the longest palindromic subsequence inside it.
A subsequence is what you get by deleting some characters (possibly none) while keeping the remaining characters in their original order. You do not need the chosen characters to be next to each other. A palindrome reads the same forwards and backwards.
So you must pick a set of positions in increasing order, such that the characters at those positions form a palindrome, and make that set as large as possible. Return only the length of that longest palindrome, not the string itself.
Key rule that drives the answer: if the first and last characters of a range are equal, they can both be used as the two ends of a palindrome. If they differ, at least one of them must be dropped.
Pick characters, keep the order
Constraints
- ●
1 <= s.length <= 1000 - ●
s consists only of lowercase English letters.
Examples
s = "bbbab"4s = "cbbd"2Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Microsoft | Medium | View all Microsoft questions → |
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
How to Think About It
Key insight: a palindromic subsequence reads the same forwards and backwards. If the first and last characters match, they both contribute to the answer: 2 + LPS of the middle. If they don't match, the answer is the max of skipping the first or skipping the last character.
Define dp[i][j] = length of longest palindromic subsequence in s[i..j]. Base case: dp[i][i] = 1 (single character is a palindrome of length 1).
Transition: if s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2. Otherwise, dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Fill by substring length from 2 to n.
Space optimization: you only need the previous row. Use a 1D array where dp[j] stores the LPS for the current row. Update from right to left to avoid overwriting. Space drops from O(n²) to O(n).
Time: O(n²) for the 2D DP. Space: O(n²) naive, O(n) optimized.
Optimal Approach
Create a 2D dp table of size n x n where dp[i][j] = LPS length of s[i..j].
- Initialize diagonal:
dp[i][i] = 1for all i. - For length = 2 to n:
a. For i = 0 to n - length:- j = i + length - 1
- If s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2 - Else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
- Return
dp[0][n-1].
Walkthrough: s = "bbbab".
- Length 1: all 1s on diagonal.
- Length 2: "bb" -> 3, "bb" -> 3, "ba" -> 1, "ab" -> 1.
- Length 3: "bbb" -> 3, "bba" -> 3, "bab" -> 3.
- Length 4: "bbba" -> 3, "bbab" -> 3.
- Length 5: "bbbab" -> dp[1][3] + 2 = 5.
Time: O(n²). Space: O(n²).
Fill the dp table by substring length
What Trips People Up in Real Interviews
Confusing subsequence with substring. A subsequence does NOT need to be contiguous. "ace" is a subsequence of "abcde" but not a substring. This is the most common misunderstanding on this problem.
Filling the DP table in the wrong order. You must fill by increasing substring length, not by row or column. If you try row-by-row, dp[i+1][j-1] hasn't been computed yet.
Forgetting the base case where i == j. A single character is a palindrome of length 1, not 0. Without this base, all your answers will be off by the number of characters.
Off-by-one errors in the length loop. The outer loop should go from length = 2 to n (inclusive), and the inner loop computes j = i + length - 1. Getting the bounds wrong causes index out of range or missed entries.
Not recognizing this as the reverse of Longest Common Subsequence. LPS(s) = LCS(s, reverse(s)). If you already know LCS, this is a one-liner. But the direct 2D DP is more efficient and what interviewers expect.
Solution Code
O(n^2) timedef longestPalindromeSubseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]Frequently Asked Questions
What is the Longest Palindromic Subsequence problem?
Given a string s, find the length of the longest palindromic subsequence. A subsequence is obtained by deleting zero or more characters without changing the order. This is a classic 2D DP problem where you compare characters from both ends of the string.
How do you solve Longest Palindromic Subsequence?
The optimal approach runs in O(n^2) time and O(n^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Longest Palindromic Subsequence?
Longest Palindromic Subsequence is asked at Microsoft, Goldman Sachs. It is a medium difficulty problem.
What are common mistakes on Longest Palindromic Subsequence?
- Confusing subsequence with substring. A subsequence does NOT need to be contiguous. "ace" is a subsequence of "abcde" but not a substring. This is the most common misunderstanding on this problem.
- Filling the DP table in the wrong order. You must fill by increasing substring length, not by row or column. If you try row-by-row, `dp[i+1][j-1]` hasn't been computed yet.
- Forgetting the base case where i == j. A single character is a palindrome of length 1, not 0. Without this base, all your answers will be off by the number of characters.
- Off-by-one errors in the length loop. The outer loop should go from length = 2 to n (inclusive), and the inner loop computes j = i + length - 1. Getting the bounds wrong causes index out of range or missed entries.
- Not recognizing this as the reverse of Longest Common Subsequence. LPS(s) = LCS(s, `reverse(s)`). If you already know LCS, this is a one-liner. But the direct 2D DP is more efficient and what interviewers expect.