Log inSign up
mediumleetcodeNot Started

Longest Palindromic Subsequence

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

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.

Example 1 · Example:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2 · Example:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master interval dynamic programming on boundary pointers.
  • Formulate LPS as LCS(s, reverse(s)).
  • Reduce 2D DP space from O(N2) to O(N).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding longest palindromic subsequence across non-contiguous characters.
  • Minimum deletions to make a string a palindrome (N - LPS(s)).

Algorithmic Decision Tree:

  • Interval 2D Dynamic Programming
  • LCS Transformation

Connected Patterns:

Longest Common SubsequenceLongest Palindromic SubstringMinimum Insertion Steps to Make a String Palindrome

1. Top-Down Recursion with 2D Memoization

Intuition

Define helper(i, j) as the length of LPS in s[i...j]. Base cases: if i > j, return 0; if i == j, return 1. If s[i] == s[j], return 2 + helper(i + 1, j - 1). Otherwise, return max(helper(i + 1, j), helper(i, j - 1)). Memoize with a 2D array memo[i][j].

When to apply: When constructing the intuitive divide-and-conquer base solution.

Algorithm

  1. Initialize memo matrix of size N x N filled with -1.
  2. Helper function solve(i, j):
  3. - If i > j: return 0.
  4. - If i == j: return 1.
  5. - If memo[i][j] != -1: return memo[i][j].
  6. - If s[i] == s[j]: memo[i][j] = 2 + solve(i + 1, j - 1).
  7. - Else: memo[i][j] = max(solve(i + 1, j), solve(i, j - 1)).
  8. - Return memo[i][j].
  9. Return solve(0, n - 1).

Top-Down Recursion with 2D Memoization

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [b, b, b, a, b]
Current operationSTEP 1 OF 6
Observation: Initial call lps(0, 4) covers the entire string 'bbbab'
Visual state
Values and pointers at this exact step
array
S
b
b
b
a
b
0
↑ i=0 ('b')
1
2
3
4
↑ j=4 ('b')
Variables at this step
i
0
j
4
charI
b
charJ
b
match
true
recurrence
2 + lps(1, 3)
Check / comparison
Evaluate lps(0, 4): s[0] == s[4] ('b' == 'b').
Decision / next transition
Characters match! Incur 2 matching endpoints and recurse on inner substring lps(1, 3).
Why this step matters

Observation: Initial call lps(0, 4) covers the entire string 'bbbab'.

Decision: Characters at both endpoints match: s[0] == s[4] == b. Recurse to 2 + lps(1, 3) on 'bba'.

Invariant: Matching endpoints contribute +2 to the maximum palindrome length.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7 int solve(int i, int j, const std::string& s, std::vector<std::vector<int>>& memo) {
8 if (i > j) return 0;
9 if (i == j) return 1;
10 if (memo[i][j] != -1) return memo[i][j];
11
12 if (s[i] == s[j]) {
13 return memo[i][j] = 2 + solve(i + 1, j - 1, s, memo);
14 } else {
15 return memo[i][j] = std::max(solve(i + 1, j, s, memo), solve(i, j - 1, s, memo));
16 }
17 }
18public:
19 int longestPalindromeSubseq(std::string s) {
20 int n = s.size();
21 std::vector<std::vector<int>> memo(n, std::vector<int>(n, -1));
22 return solve(0, n - 1, s, memo);
23 }
24};
25
26int main() {
27 Solution sol;
28 std::cout << sol.longestPalindromeSubseq("bbbab") << std::endl; // 4
29 std::cout << sol.longestPalindromeSubseq("cbbd") << std::endl; // 2
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N^2) — There are N * (N + 1) / 2 unique states, each computed in O(1) time.
  • Space complexity: O(N^2) memo + O(N) recursion stack

Why Brute Force Doesn't Scale:

Interval DP with 1D compression maintains optimal O(N2) time while cutting space from O(N2) to O(N).

Using a single 1000-element array consumes under 4 KB of RAM.

2. Bottom-Up 2D Table DP (Interval Iteration)

Intuition

Initialize dp[n][n] where dp[i][i] = 1. Iterate i from n - 1 down to 0, and j from i + 1 to n - 1. If s[i] == s[j], dp[i][j] = 2 + dp[i + 1][j - 1]. Otherwise, dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]). The answer is stored in dp[0][n - 1].

When to apply: Standard iterative dynamic programming formulation.

Algorithm

  1. Initialize dp[n][n] = 0.
  2. For i from n - 1 down to 0:
  3. dp[i][i] = 1
  4. For j from i + 1 to n - 1:
  5. If s[i] == s[j]: dp[i][j] = 2 + dp[i + 1][j - 1].
  6. Else: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
  7. Return dp[0][n - 1].

Bottom-Up 2D Table DP (Interval Iteration)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [b, b, b, a, b]
Current operationSTEP 1 OF 6
Observation: Construct a 2D table dp[N][N] where dp[i][j] is the LPS length in s[i
Visual state
Values and pointers at this exact step
array
S
b
b
b
a
b
0
↑ BASE CASES: dp[i][i] = 1
1
2
3
4
Variables at this step
diagonalFilled
true
len
1
baseValue
1
Check / comparison
Initialize 5x5 DP table. Length 1 substrings are palindromes of length 1.
Decision / next transition
Set dp[i][i] = 1 for all i in [0..4].
Why this step matters

Observation: Construct a 2D table dp[N][N] where dp[i][j] is the LPS length in s[i..j].

Decision: Every single character is a palindrome of length 1: dp[i][i] = 1.

Invariant: Base cases fill the main diagonal of the DP matrix.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 int longestPalindromeSubseq(std::string s) {
9 int n = s.size();
10 std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
11
12 for (int i = n - 1; i >= 0; --i) {
13 dp[i][i] = 1;
14 for (int j = i + 1; j < n; ++j) {
15 if (s[i] == s[j]) {
16 dp[i][j] = 2 + dp[i + 1][j - 1];
17 } else {
18 dp[i][j] = std::max(dp[i + 1][j], dp[i][j - 1]);
19 }
20 }
21 }
22 return dp[0][n - 1];
23 }
24};
25
26int main() {
27 Solution sol;
28 std::cout << sol.longestPalindromeSubseq("bbbab") << std::endl; // 4
29 std::cout << sol.longestPalindromeSubseq("cbbd") << std::endl; // 2
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N^2) — Iterates through all upper-triangular matrix cells.
  • Space complexity: O(N^2)

3. Space-Optimized 1D Rolling DP (O(N) Space)

Intuition

Observe that calculating the row i only depends on the row below (i + 1). Maintain a 1D array dp of size N. As we iterate j from i + 1 to n - 1, the value dp[j] represents dp[i+1][j] (from the previous row), and dp[j-1] represents dp[i][j-1] (just updated in the current row). We keep prev = dp[j] before updating dp[j] so prev acts as dp[i+1][j-1].

When to apply: Optimal benchmark for minimal memory footprint and maximum cache locality.

Algorithm

  1. Initialize dp array of size N with 0.
  2. Loop i from n - 1 down to 0:
  3. Set dp[i] = 1 and prev = 0.
  4. For j from i + 1 to n - 1:
  5. temp = dp[j]
  6. If s[i] == s[j]: dp[j] = 2 + prev.
  7. Else: dp[j] = max(dp[j], dp[j - 1]).
  8. prev = temp
  9. Return dp[n - 1].

2D Dynamic Programming Interval Table Fill

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [b, b, b, a, b]
Current operationSTEP 1 OF 6
Observation: Every single character is trivially a palindrome of length 1
Visual state
Values and pointers at this exact step
array
S
b
b
b
a
b
0
↑ Base case: len=1
1
2
3
4
Variables at this step
baseCaseLength
1
dpDiag
dp[i][i] = 1 for all i in [0..4]
Why this step matters

Observation: Every single character is trivially a palindrome of length 1.

Decision: Initialize dp[i][i] = 1 across all 5 indices.

Invariant: Base case intervals of length 1 established.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 int longestPalindromeSubseq(std::string s) {
9 int n = s.size();
10 std::vector<int> dp(n, 0);
11
12 for (int i = n - 1; i >= 0; --i) {
13 dp[i] = 1;
14 int prev = 0;
15 for (int j = i + 1; j < n; ++j) {
16 int temp = dp[j];
17 if (s[i] == s[j]) {
18 dp[j] = 2 + prev;
19 } else {
20 dp[j] = std::max(dp[j], dp[j - 1]);
21 }
22 prev = temp;
23 }
24 }
25 return dp[n - 1];
26 }
27};
28
29int main() {
30 Solution sol;
31 std::cout << sol.longestPalindromeSubseq("bbbab") << std::endl; // 4
32 std::cout << sol.longestPalindromeSubseq("cbbd") << std::endl; // 2
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N^2) — Performs N2 / 2 state transitions using a single N-length array.
  • Space complexity: O(N) extra space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Top-Down Recursion with MemoizationO(N^2)O(N^2) memo + O(N) call stackNatural translation of recursive recurrence relation.Recursion call overhead.
2.Bottom-Up 2D Table Interval DPO(N^2)O(N^2)Clean iterative table filling without recursion limit risk.Allocates full N x N matrix.
3.Space-Optimized 1D Rolling DP (Optimal)OptimalO(N^2)O(N) memoryOptimal linear memory footprint with high cache efficiency.Requires tracking previous diagonal value dp[i+1][j-1] in a temporary variable.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Confusing Longest Palindromic Subsequence (DP, non-contiguous) with Longest Palindromic Substring (expand around centers, contiguous).

Pitfall 2:

Forward iteration on i which accesses uncomputed subproblems dp[i+1][j].

Crucial Edge Cases to Validate:

  • Single character string (s = a): Length is 1, loop executes with dp[0]=1, returns 1.
  • All identical characters (s = aaaa): Every pair matches, returns length of string n.
  • No matching characters except singles (s = abcdef): dp returns 1 (any single character is a palindrome of length 1).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight both Interval DP and LCS(s, reverse(s)) formulations to demonstrate multiple perspective problem-solving.
  2. Derive the 1D space optimization on the whiteboard using the prev diagonal cache variable.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How is Longest Palindromic Subsequence (LPS) related to Longest Common Subsequence (LCS)?

Back to DSA Sheet