Longest Palindromic Subsequence
Asked at Microsoft
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Microsoft | Medium | View all Microsoft 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.
Visual walkthrough for s = "bbbab":
dp table (5x5), i = row, j = col:
Diagonal = 1 (base case).
Length 2: dp[0][1]="bb" -> match, dp+2 = 3. dp[1][2]="bb" -> match, 3. dp[2][3]="ba" -> no, max(1,1)=1. dp[3][4]="ab" -> no, max(1,1)=1.
Length 3: dp[0][2]="bbb" -> match, dp[1][1]+2=3. dp[1][3]="bba" -> no, max(3,1)=3. dp[2][4]="bab" -> match, dp[3][3]+2=3.
Length 4: dp[0][3]="bbba" -> no, max(3,3)=3. dp[1][4]="bbab" -> no, max(3,3)=3.
Length 5: dp[0][4]="bbbab" -> match, dp[1][3]+2=5. Result: 5 ("bbbb").
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²).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Palindromic Subsequence?
Longest Palindromic Subsequence is asked at Microsoft. 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.