Skip to main content
Talentd

Longest Palindromic Subsequence - Solution & Explanation

MediumStringDynamic Programming17 min readAsked at: Amazon, Microsoft, Goldman Sachs +12
Practice this problem

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:

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".

 

Constraints:

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

Approach Overview

Problem Overview: Given a string s, return the length of the longest subsequence that reads the same forward and backward. Unlike substrings, subsequences do not need to be contiguous, so you can skip characters while preserving order.

This problem appears frequently in string and dynamic programming interviews. The key observation: if the first and last characters of a substring match, they can contribute to a palindrome. Otherwise, you must skip one side and try smaller subproblems.

Approach 1: Recursive Approach with Memoization (Top-Down DP) (Time: O(n2), Space: O(n2))

Define a recursive function dfs(i, j) that returns the longest palindromic subsequence within the substring s[i..j]. If s[i] == s[j], those characters form the ends of a palindrome, so the answer becomes 2 + dfs(i+1, j-1). If they differ, skip one side and compute max(dfs(i+1, j), dfs(i, j-1)). Without optimization this recursion explodes exponentially, because the same ranges repeat many times.

Memoization fixes this by caching results for each pair (i, j). Since there are only n * n possible substrings, the recursion runs in O(n²) time and stores results in an O(n²) memo table. This approach is intuitive because it mirrors the mathematical recurrence directly.

Approach 2: Dynamic Programming (Bottom-Up Table) (Time: O(n2), Space: O(n2))

The bottom-up version fills a DP table where dp[i][j] represents the length of the longest palindromic subsequence in s[i..j]. Start with base cases where every single character is a palindrome of length 1. Then expand the window size from smaller substrings to larger ones.

For each pair of indices:

If s[i] == s[j], extend the inner palindrome: dp[i][j] = 2 + dp[i+1][j-1]. If they differ, carry forward the best subsequence by skipping one side: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

The table is typically filled from the bottom of the string toward the start so that subproblems like dp[i+1][j-1] are already computed. This produces the final answer at dp[0][n-1]. Because every substring pair is processed exactly once, the runtime is O(n²) and the memory cost is also O(n²).

Another useful insight: the problem is equivalent to computing the Longest Common Subsequence between the string and its reverse. That perspective often helps when connecting multiple dynamic programming patterns together.

Recommended for interviews: The bottom-up dynamic programming approach is what most interviewers expect. It shows you understand overlapping subproblems, table construction, and state transitions. Starting with the recursive relation demonstrates intuition, then converting it to memoization or a DP table shows strong problem‑solving discipline.

Approach 1: Dynamic Programming Approach

Use a 2D table to keep track of the longest palindromic subsequence. The idea is to fill out this table by solving smaller subproblems and using their results to build up solutions to bigger ones.

The table, dp[i][j], will store the length of the longest palindromic subsequence in s[i...j]. Start by assuming that each character is a palindrome of length 1, and fill the table based on whether the characters at the current indices are the same.

We initialize a 2D table with zero values and then iterate over the string in reverse to ensure that we only use already computed values for dp[i+1][j] and dp[i][j-1] when needed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the length of the string, because we need to fill an n x n table.
Space Complexity: O(n^2), for the same reason due to the dp table.

Try this approach in the editor →

Approach 2: Recursive Approach with Memoization

This approach defines a recursive function that explores all potential palindromic subsequences, using memoization to store results of overlapping subproblems, thereby avoiding redundant calculations. The function checks if the characters at current indices are equal and proceeds based on that, with memoization avoiding recalculations.

In the recursive approach, a helper function checks the characters from both ends of the string, memoizing already computed results to reduce computational overhead. The "memo" array stores results of already solved subproblems.

Code

PythonJavaC++C#JavaScript

Python

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the length of the string due to memoization.
Space Complexity: O(n^2) for the memoization table.

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i][j] as the length of the longest palindromic subsequence from the i-th character to the j-th character in string s. Initially, f[i][i] = 1, and the values of other positions are all 0.

If s[i] = s[j], then f[i][j] = f[i + 1][j - 1] + 2; otherwise, f[i][j] = max(f[i + 1][j], f[i][j - 1]).

Since the value of f[i][j] is related to f[i + 1][j - 1], f[i + 1][j], and f[i][j - 1], we should enumerate i from large to small, and enumerate j from small to large.

The answer is f[0][n - 1].

The time complexity is O(n^2), and the space complexity is O(n^2). Where n is the length of the string s.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n^2), where n is the length of the string, because we need to fill an n x n table.
Space Complexity: O(n^2), for the same reason due to the dp table.

Recursive Approach with Memoization

Time Complexity: O(n^2), where n is the length of the string due to memoization.
Space Complexity: O(n^2) for the memoization table.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive with Memoization (Top-Down DP)O(n^2)O(n^2)When you want a direct implementation of the recursive recurrence and easier reasoning about subproblems.
Dynamic Programming Table (Bottom-Up)O(n^2)O(n^2)Preferred in interviews for predictable iteration order and avoiding recursion overhead.

Video Solution

DP 28. Longest Palindromic Subsequence • take U forward • 457,926 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Palindromic Subsequence easy or hard?
The problem is classified as Medium because recognizing the DP state is the main challenge. Once you identify dp[i][j] for substring ranges and define the correct recurrence, the implementation becomes straightforward.
Longest Palindromic Subsequence Python/Java solution
Most implementations use a 2D DP array or memoization map. Python solutions typically use a list-of-lists DP table or functools.lru_cache for recursion, while Java solutions use a 2D int array and nested loops to fill substring ranges.
How to solve Longest Palindromic Subsequence in O(n^2)?
Use dynamic programming over substrings. Define dp[i][j] as the longest palindromic subsequence between indices i and j. If s[i] equals s[j], extend the inner result with 2 + dp[i+1][j-1]; otherwise take max(dp[i+1][j], dp[i][j-1]). Filling the table for all pairs yields an O(n^2) solution.
What is the best approach for Longest Palindromic Subsequence?
Dynamic programming is the standard approach. Build a DP table where dp[i][j] represents the longest palindromic subsequence in substring s[i..j]. By comparing characters at both ends and reusing previously computed results, the solution runs in O(n^2) time with O(n^2) space.
Is Longest Palindromic Subsequence asked at Google/Amazon/Meta?
Longest Palindromic Subsequence appears frequently in interviews at companies like Amazon, Google, and Meta because it tests dynamic programming fundamentals. Candidates must identify overlapping subproblems and design the correct DP state transition.
What data structure is used in Longest Palindromic Subsequence?
The primary data structure is a 2D dynamic programming table (matrix) that stores results for substring ranges. In top-down solutions, the same structure appears as a memoization cache keyed by index pairs.
What is the time complexity of Longest Palindromic Subsequence?
The optimal dynamic programming solution runs in O(n^2) time because every substring pair (i, j) is evaluated once. The DP table stores results for n^2 states, leading to O(n^2) space complexity as well.

Ready to solve this problem?

Practice Longest Palindromic Subsequence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Different Palindromic Subsequences

Next

Longest Common Subsequence