Longest Palindromic Subsequence

20
16

Problem Statement

Given a string s, find the length of the longest palindromic subsequence. A subsequence may skip characters but must preserve the relative order of every selected character. Selected characters do not need to occupy adjacent positions.

Example 1

Input: s = "bbbab"
Output: 4
Explanation: "bbbb" is a palindromic subsequence of length 4, formed by preserving the order of four selected b characters.

Example 2

Input: s = "a"
Output: 1
Explanation: A single character already reads identically in both directions, so the longest palindromic subsequence has length 1.

Recursion

Start with the two ends of the current string range. Matching end characters fit together as the outer pair of a palindrome, so both characters can be kept and attention can move inward. Different end characters cannot both form the outer pair, so one end must be skipped.

The state solve(left, right) stores the best palindromic subsequence length inside s[left...right]. The first call uses solve(0, n - 1) because the initial state must cover the complete string. Smaller ranges repeat until an empty range contributes 0 or a one-character range contributes 1.

Algorithm

  • Begin with solve(0, n - 1) so the first recursive state covers every character in the string.

  • Return 0 when left > right because an empty range contributes no character to a palindrome.

  • Return 1 when left == right because a single character forms a palindrome without another matching character.

  • Keep both end characters when s[left] == s[right], then add 2 to the inner range answer because the matching pair can surround every inner palindrome.

  • Skip the left character after different end characters because a valid outer pair may still begin at left + 1.

  • Skip the right character for the symmetric alternative because a valid outer pair may still end at right - 1.

  • Return the larger skip result after a mismatch because the longer valid subsequence gives the required answer for the current range.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds the best length inside one string range.
int solve(int left, int right, string& s) {
// An empty range adds no palindrome character.
if (left > right) {
return 0;
}
// One character forms a palindrome of length one.
if (left == right) {
return 1;
}
// Equal ends can surround every inner palindrome.
if (s[left] == s[right]) {
// Both matching ends extend the inner answer.
return 2 + solve(left + 1, right - 1, s);
}
// Skipping the left end keeps the right end.
int skipLeft = solve(left + 1, right, s);
// Skipping the right end keeps the left end.
int skipRight = solve(left, right - 1, s);
// The longer valid exclusion gives the best answer.
return max(skipLeft, skipRight);
}
public:
// Finds the longest palindromic subsequence length.
int longestPalindromeSubseq(string s) {
int n = s.size();
// An empty string has no selected character.
if (n == 0) {
return 0;
}
// The first state covers the complete string.
return solve(0, n - 1, s);
}
};
// Driver code
int main() {
string s = "bbbab";
Solution obj;
cout << obj.longestPalindromeSubseq(s) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(2N), where N is the string length, because a mismatched range can create two recursive branches while each branch removes one character from the range.

Space Complexity: O(N), because the deepest recursive path can contain at most N calls on the recursion stack.

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Memoization

Direct recursion reaches the same interval through different skip orders. For example, skipping the left end and later skipping the right end can reach the same solve(left, right) state as the opposite order. Recomputing an unchanged string range adds no new information.

A two-dimensional dp array saves the answer for every pair of boundaries. The recursive state and every transition remain unchanged; only a cache lookup and a cache write are added. A stored value turns an entire repeated recursion subtree into one constant-time lookup.

Algorithm

  • Begin with an n x n array named dp, filled with -1, so every untouched interval is clearly marked as uncalculated.

  • Start from solve(0, n - 1) because the complete string still represents the original problem.

  • Return 0 for an empty range and 1 for a one-character range because both base values are already known without cache storage.

  • Reuse dp[left][right] when a stored value exists because the same boundaries always describe the same substring problem.

  • Keep both matching ends and add 2 to the inner answer because equal characters can surround the best inner palindrome.

  • Compare both one-end exclusions after a mismatch because either boundary may block a longer palindromic subsequence.

  • Store the computed result in dp[left][right] before returning so every later visit avoids repeated recursive work.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds and caches one string range answer.
int solve(int left, int right, string& s,
vector<vector<int>>& dp) {
// An empty range adds no palindrome character.
if (left > right) {
return 0;
}
// One character forms a palindrome of length one.
if (left == right) {
return 1;
}
// A stored range avoids repeated recursion.
if (dp[left][right] != -1) {
return dp[left][right];
}
// Equal ends can surround every inner palindrome.
if (s[left] == s[right]) {
// Both matching ends extend the inner answer.
int answer = 2 + solve(
left + 1, right - 1, s, dp
);
// Cache storage preserves the completed range.
dp[left][right] = answer;
return dp[left][right];
}
// Skipping the left end keeps the right end.
int skipLeft = solve(left + 1, right, s, dp);
// Skipping the right end keeps the left end.
int skipRight = solve(left, right - 1, s, dp);
// The longer exclusion becomes the cached answer.
dp[left][right] = max(skipLeft, skipRight);
return dp[left][right];
}
public:
// Finds the longest palindromic subsequence length.
int longestPalindromeSubseq(string s) {
int n = s.size();
// An empty string has no selected character.
if (n == 0) {
return 0;
}
// Minus one marks every uncalculated range.
vector<vector<int>> dp(
n, vector<int>(n, -1)
);
// The first state covers the complete string.
return solve(0, n - 1, s, dp);
}
};
// Driver code
int main() {
string s = "bbbab";
Solution obj;
cout << obj.longestPalindromeSubseq(s) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the string length, because at most N × N boundary pairs are computed once, with constant work per state.

Space Complexity: O(N2), because the dp table stores up to N × N answers, while the recursion stack adds O(N) calls along the deepest path.

Tabulation

Memoization proves every answer depends only on smaller intervals. Tabulation computes the same states in an order guaranteeing every inner or shortened range already has a value. Recursive calls disappear, along with the recursion stack.

The two-dimensional dp array keeps the same meaning: dp[left][right] stores the best length inside s[left...right]. Left boundaries move from right to left, while right boundaries move from left + 1 toward the end. Such an order makes dp[left + 1][right - 1], dp[left + 1][right], and dp[left][right - 1] available before the current cell.

Algorithm

  • Return 0 immediately for an empty string because no table cell can represent an empty full input.

  • Create an n x n array named dp, filled with 0, so empty inner ranges already contribute the required zero value.

  • Set every diagonal value dp[index][index] to 1 because each one-character interval forms a palindrome.

  • Move left from n - 1 down to 0 so every state from the next row is ready before the current row needs the answer.

  • Move right from left + 1 up to n - 1 so the current row value on the left is also ready.

  • Add 2 to dp[left + 1][right - 1] after matching ends because the equal characters surround the best inner palindrome.

  • Store the maximum of dp[left + 1][right] and dp[left][right - 1] after a mismatch because different ends cannot surround one palindrome, then return dp[0][n - 1] as the complete-string answer.

Dry Run

longest-palindromic-subsequence-tabulation.png

longest-palindromic-subsequence-tabulation.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the longest palindromic subsequence length.
int longestPalindromeSubseq(string s) {
int n = s.size();
// An empty string has no selected character.
if (n == 0) {
return 0;
}
// Zero also represents every empty inner range.
vector<vector<int>> dp(
n, vector<int>(n, 0)
);
// Every one-character range is a palindrome.
for (int index = 0; index < n; index++) {
dp[index][index] = 1;
}
// Descending left values prepare the next row.
for (int left = n - 1; left >= 0; left--) {
// Ascending right values prepare the row left.
for (int right = left + 1;
right < n; right++) {
// Equal ends surround the inner answer.
if (s[left] == s[right]) {
// The recursive inner state becomes dp.
dp[left][right] =
2 + dp[left + 1][right - 1];
} else {
// Both one-end exclusions are ready.
dp[left][right] = max(
dp[left + 1][right],
dp[left][right - 1]
);
}
}
}
// The top-right cell covers the full string.
return dp[0][n - 1];
}
};
// Driver code
int main() {
string s = "bbbab";
Solution obj;
cout << obj.longestPalindromeSubseq(s) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the string length, because the nested loops compute each valid pair of string boundaries once with constant work per table cell.

Space Complexity: O(N2), because the two-dimensional dp table stores one answer for every possible pair of string boundaries, with no recursion stack.

Space Optimization

Each tabulation cell needs only three earlier values: the cell below, the cell to the left, and the previous row's diagonal cell. A one-dimensional dp array can keep the previous row before an update and the current row after an update. Full older rows never appear in a later transition.

For a fixed left, dp[right] initially represents dp[left + 1][right], while dp[right - 1] already represents dp[left][right - 1]. A variable named previousDiagonal preserves the old dp[left + 1][right - 1] value. Saving the old below value before overwriting dp[right] provides the next diagonal after the right boundary moves.

Algorithm

  • Return 0 for an empty string because no one-dimensional state exists for a missing character.

  • Create a one-dimensional array named dp, filled with 0, so previous-row and empty-range values begin with the correct neutral length.

  • Move left from n - 1 down to 0, set dp[left] = 1, and reset previousDiagonal = 0 because the current diagonal is a one-character palindrome.

  • Move right from left + 1 toward n - 1 so dp[right - 1] already belongs to the current row.

  • Save the old dp[right] as below before any update because the same value becomes the diagonal needed by the next right boundary.

  • Calculate current from previousDiagonal + 2 for matching ends or from max(dp[right], dp[right - 1]) for different ends because the two cases preserve the original interval transition.

  • Write current into dp[right], then shift below into previousDiagonal in the stated order so no required previous-row value is lost.

  • Return dp[n - 1] because the final left-boundary pass expands the stored answer across the complete string.

Dry Run

Longest Palindromic Subsequence Space Optimization

Longest Palindromic Subsequence Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the longest palindromic subsequence length.
int longestPalindromeSubseq(string s) {
int n = s.size();
// An empty string has no selected character.
if (n == 0) {
return 0;
}
// Values begin as empty-range answers.
vector<int> dp(n, 0);
// Descending left values build one row in place.
for (int left = n - 1; left >= 0; left--) {
// Zero represents the empty inner diagonal.
int previousDiagonal = 0;
// A diagonal cell represents one character.
dp[left] = 1;
// Ascending right values preserve the row left.
for (int right = left + 1;
right < n; right++) {
// The old value is the cell below.
int below = dp[right];
int current;
// Equal ends extend the saved diagonal.
if (s[left] == s[right]) {
// Current recreates the matching transition.
current = previousDiagonal + 2;
} else {
// Current compares both shortened ranges.
current = max(dp[right], dp[right - 1]);
}
// The active position stores the current row.
dp[right] = current;
// The saved below value shifts diagonally.
previousDiagonal = below;
}
}
// The last position covers the full string.
return dp[n - 1];
}
};
// Driver code
int main() {
string s = "bbbab";
Solution obj;
cout << obj.longestPalindromeSubseq(s) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the number of elements, because the nested boundary loops process every valid interval once with constant work per interval.

Space Complexity: O(N), because the one-dimensional dp array stores one value for each position, while two scalar variables preserve the dependencies overwritten during the update.

Interview follow-up Questions

A subsequence preserves relative order but may skip positions. A substring requires consecutive positions. For s = "bbbab", "bbbb" is a subsequence even though one nonselected character lies between selected characters.

Dynamic ProgrammingTCS NQT

Read Similar Blogs

Comments0