Loading…

mediumDynamic ProgrammingLC #516Frequently asked

Longest Palindromic Subsequence

Q: How do you solve Longest Palindromic Subsequence using the Brute Force — Recursion Matching the Two Ends approach?

When to use it: Say this first to establish the two-case interval recurrence (ends match vs differ), then flag the exponential overlap. Define `solve(i, j)` = length of the longest palindromic subsequence of the window `s[i..j]`. - If `i > j` the window is empty → 0. - If `i == j` it's a single character, itself a palindrome → 1. - If `s[i] == s[j]`, both ends can serve as the outer pair of a palindrome, contributing 2, and the rest comes from the inner window: `2 + solve(i+1, j-1)`. - Otherwise the ends differ; at least one of them cannot be an outer matched character, so drop one and take the better side: `max(solve(i+1, j), solve(i, j-1))`. **The mental shift: decide the fate of the two boundary characters.** A palindrome is defined by its symmetry around the center, so the natural question at any window is what happens at its outermost characters. If they're equal, the greedy-looking move — pair them up and recurse inward — is provably optimal: any palindromic subsequence of `[i, j]` can be extended to use both equal ends without getting shorter. If they're unequal, they can't both be the matched outer pair, so the optimum must ignore at least one of them, which is exactly the two `max` branches. **Why `+2`, not `+1` or `max`, when the ends match.** Both `s[i]` and `s[j]` join the palindrome — one on the left flank, one on the right — so they add two characters, and the inner window is solved independently. Using `max` here (a classic slip) throws away the guaranteed pair and undercounts. **Why we don't ship this.** The two `max` branches overlap enormously — `solve(i+1, j)` and `solve(i, j-1)` both recurse into `solve(i+1, j-1)`, and so on — so the same window is recomputed exponentially many times. Caching `solve(i, j)` collapses it to `O(n²)`. Time complexity: O(2ⁿ). Space complexity: O(n).

Q: How do you solve Longest Palindromic Subsequence using the Top-Down Memoization on (i, j) approach?

When to use it: The fix once you name the overlap — 'cache solve(i, j) so each window is computed once'. Keep the end-matching recurrence but cache `solve(i, j)` in a 2-D table so each window is solved once. **The mental shift: a window's LPS depends only on its endpoints.** However you arrived at `[i, j]`, the longest palindromic subsequence inside it is a fixed number. Caching by `(i, j)` removes all the duplicated work. There are `O(n²)` windows and each costs `O(1)` to resolve given its sub-results, so the bound is `O(n²)` directly. **Choosing the sentinel.** Initialise the memo to -1 for 'uncomputed' — real LPS lengths are non-negative, so -1 is unambiguous. The `i == j` base returns 1 and `i > j` returns 0 before any lookup. **A language note (Java memo vs Python tabulation).** Recursion here nests up to `O(n)` deep. With `n` as large as 1000 (the constraint), that depth approaches **Python's default recursion limit of about 1000**, so a deep, skewed input can overflow the stack. In Java that depth is fine. So in Python you'd either raise the limit with `sys.setrecursionlimit` or prefer the bottom-up table (next approach), which has no recursion at all. Top-down memoization is the comfortable default in Java; tabulation is the safer default in Python at this size. Time complexity: O(n²). Space complexity: O(n²).

Q: How do you solve Longest Palindromic Subsequence using the Bottom-Up — Interval DP by Increasing Length (Optimal) approach?

When to use it: The answer they want. Frame it as 'fill dp[i][j] so the inner window [i+1][j-1] is ready', and mention the LCS(s, reverse) alternative. Build `dp[i][j]` = LPS of `s[i..j]` so that every window's dependencies are finalised before it. Seed the diagonal `dp[i][i] = 1`. Then for each window length from 2 to n, set `i`, compute `j = i + length - 1`, and apply the recurrence; the answer is `dp[0][n-1]`. **The dependency order.** `dp[i][j]` reads `dp[i+1][j-1]` (inner window, two shorter), `dp[i+1][j]` and `dp[i][j-1]` (one shorter each). All are strictly shorter intervals, so filling by increasing length guarantees they're ready. Equivalently, iterate `i` from `n-1` down to `0` (outer) and `j` from `i+1` up to `n-1` (inner) — this also visits `[i+1][*]` before `[i][*]`. Either ordering avoids reading an unfilled cell. **The recurrence in table terms.** If `s[i] == s[j]`, the two ends pair up: `dp[i][j] = 2 + dp[i+1][j-1]`. Otherwise drop one end: `dp[i][j] = max(dp[i+1][j], dp[i][j-1])`. The diagonal of 1s anchors everything, exactly like the single-matrix base in Matrix Chain. **The reverse-LCS reduction.** A palindromic subsequence of `s` reads identically in `s` and in `reverse(s)`, so the longest one is precisely the Longest Common Subsequence of `s` and `reverse(s)`. If you already have an LCS routine, `LPS(s) = LCS(s, reverse(s))` is a two-line solution with the same `O(n²)` cost. Mention both framings — the interval DP shows you understand the structure; the reduction shows breadth. **Space compression.** Because `dp[i][*]` depends only on `dp[i+1][*]` and earlier cells in the same row, keep two rows for `O(n)` space. **Why bottom-up here.** With `n` up to 1000, the table fill has no recursion, so it sidesteps Python's stack-depth limit entirely — the practical reason to prefer it in Python. Time complexity: O(n²). Space complexity: O(n) with a rolling row.

LCPractice

Dynamic Programming · 29 of 44 · 12 min

Given a string s, find the length of the **longest palindromic subsequence** in s.

A subsequence is a sequence derived from s by deleting zero or more characters without changing the order of the remaining characters. A palindrome reads the same forwards and backwards.

Return the length of the longest such subsequence (you do not need to return the subsequence itself).

In plain English

Picture choosing characters from s, keeping their order, so the chosen sequence is a palindrome — and make it as long as possible. Working from the two ends inward: if the first and last characters of the current window are equal, they can both sit at the outside of a palindrome, contributing 2 and leaving the inner window to solve. If they differ, at least one of them can't be a matched outer pair, so you discard one end and take whichever side gives more. The state is the window [i, j], which is exactly an interval DP.

Examples

Example 1

Input: s = "bbbab"
Output: 4
Note: The subsequence 'bbbb' (indices 0,1,2,4) is a palindrome of length 4. You can't reach 5 because of the single 'a'.

Example 2

Input: s = "cbbd"
Output: 2
Note: 'bb' is the longest palindromic subsequence.

Example 3

Input: s = "agbdba"
Output: 5
Note: 'abdba' (drop the 'g') is a palindrome of length 5.

Constraints

1 ≤ s.length ≤ 1000
s consists only of lowercase English letters
The answer is at least 1 (any single character is a palindrome of length 1)
Subsequence (deletions allowed), not substring (contiguous)

Clarifying questions4First question: Subsequence or substring?Explore questions

Q1.Subsequence or substring?
Subsequence — deletions are allowed, the characters needn't be contiguous. 'bbbab' has LPS 4 ('bbbb'), even though those b's aren't adjacent.
Q2.Do I return the length or the actual palindrome?
Just the length here. Reconstructing the subsequence means walking the DP table backward from dp[0][n-1].
Q3.Is the empty string possible?
Constraints say length ≥ 1, so the answer is at least 1. An empty interval would contribute 0 in the recurrence.
Q4.Is there a slick reduction?
Yes — the LPS of s equals the LCS of s and reverse(s). Same O(n²) cost, sometimes easier to code if you already have an LCS routine.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find the longest subsequence of s that reads the same forwards and backwards. Two equivalent framings: (1) interval DP where dp[i][j] is the LPS length of s[i..j] — if the ends match, dp[i][j] = 2 + dp[i+1][j-1], else max(dp[i+1][j], dp[i][j-1]); base dp[i][i] = 1; (2) the LCS of s and reverse(s). Both are O(n²) time. The interval view is the cleaner derivation; the reverse-LCS view is the slickest one-liner reduction.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise an interval DP on [i, j], handle the two cases (ends equal → +2 and shrink both; ends differ → drop one end), and can connect it to LCS of s and its reverse.

Where candidates slip

Solving Longest Palindromic SUBSTRING by mistake, using max() when the ends match instead of adding 2, or filling the table in an order where [i+1][j-1] isn't ready yet.

How to stand out

Offer both derivations — the direct interval DP and the LCS(s, reverse(s)) reduction — and note that minimum insertions to make s a palindrome equals n − LPS, showing you see the family of problems.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion Matching the Two Ends	`O(2ⁿ)`	`O(n)`	Say this first to establish the two-case interval recurrence (ends match vs differ), then flag the exponential overlap.	Read
2	Top-Down Memoization on (i, j)	`O(n²)`	`O(n²)`	The fix once you name the overlap — 'cache solve(i, j) so each window is computed once'.	Read
3	Bottom-Up — Interval DP by Increasing Length (Optimal)Optimal	`O(n²)`	`O(n) with a rolling row`	The answer they want. Frame it as 'fill dp[i][j] so the inner window [i+1][j-1] is ready', and mention the LCS(s, reverse) alternative.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewLongest palindrome in sContiguous (substring)?YesNo, subsequenceExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion Matching the Two Ends

TimeO(2ⁿ)SpaceO(n)

Say this first to establish the two-case interval recurrence (ends match vs differ), then flag the exponential overlap.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at the two ends of the current window s[i..j]. If s[i] == s[j], can both characters be part of the same palindrome? What's left to solve?

2Hint 2Explore hint

If the ends match, they wrap a palindrome: count 2 and recurse on the inner window [i+1, j-1]. If they differ, at least one end is useless — drop one side.

3Hint 3Explore hint

When the ends differ, try both: solve(i+1, j) and solve(i, j-1), and take the max. Base cases: i > j → 0, i == j → 1.

A · Core idea

Define solve(i, j) = length of the longest palindromic subsequence of the window s[i..j].

If i > j the window is empty → 0.
If i == j it's a single character, itself a palindrome → 1.
If s[i] == s[j], both ends can serve as the outer pair of a palindrome, contributing 2, and the rest comes from the inner window: 2 + solve(i+1, j-1).
Otherwise the ends differ; at least one of them cannot be an outer matched character, so drop one and take the better side: max(solve(i+1, j), solve(i, j-1)).

The mental shift: decide the fate of the two boundary characters. A palindrome is defined by its symmetry around the center, so the natural question at any window is what happens at its outermost characters. If they're equal, the greedy-looking move — pair them up and recurse inward — is provably optimal: any palindromic subsequence of [i, j] can be extended to use both equal ends without getting shorter. If they're unequal, they can't both be the matched outer pair, so the optimum must ignore at least one of them, which is exactly the two max branches.

Why `+2`, not `+1` or `max`, when the ends match. Both s[i] and s[j] join the palindrome — one on the left flank, one on the right — so they add two characters, and the inner window is solved independently. Using max here (a classic slip) throws away the guaranteed pair and undercounts.

Why we don't ship this. The two max branches overlap enormously — solve(i+1, j) and solve(i, j-1) both recurse into solve(i+1, j-1), and so on — so the same window is recomputed exponentially many times. Caching solve(i, j) collapses it to O(n²).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "bab"

solve(0,2): s[0]='b'==s[2]='b'

2 + solve(1,1)

Stateends matched

Final result3

C · Code with teaching comments

Reference implementation previewpublic int longestPalindromeSubseq(String s) { return solve(s, 0, s.length() - 1); } // LPS length of s[i..j]Explore the full code

solution.javaJava

Brute Force — Recursion Matching the Two Ends — reference

3 teaching notes

1
public int longestPalindromeSubseq(String s) {
2
    return solve(s, 0, s.length() - 1);
3
}
4
 
5
// LPS length of s[i..j]
6
private int solve(String s, int i, int j) {
7
    if (i > j) {
8
        return 0;
9
    }
10
    // A single character is a palindrome of length 1 — the diagonal base case.
11
    if (i == j) {
12
        return 1;
13
    }
14
    if (s.charAt(i) == s.charAt(j)) {
15
        // Matching ends both join the palindrome — add 2 and shrink the window on both
16
        // sides.
17
        return 2 + solve(s, i + 1, j - 1);
18
    }
19
    // Differing ends: drop the left or the right end, keep the better side.
20
    return Math.max(solve(s, i + 1, j), solve(s, i, j - 1));
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

The state is the window (i, j) — a contiguous interval — and the recursion repeatedly revisits the same window through different end-dropping choices. Interval state plus heavy overlap is the textbook signal for an O(n²) interval DP.

ComplexityO(2ⁿ) time, O(n) space — When the ends differ the recursion forks into two overlapping subproblems; the unmemoized tree is exponential. Recursion depth is O(n).

E · Edge cases and pitfalls5single character — i == j → 1.Explore edge cases

Edge cases handled

single characteri == j → 1.
all identical charactersEvery end pair matches, recursing straight inward → returns n.

Pitfalls

Using max() when the ends match instead of adding 2 — silently undercounts.
Forgetting the i > j empty-window base case — infinite recursion or wrong counts on even-length matches.
Skipping this approach — verbalising the end-matching recurrence is what the interviewer wants.

03.2

Approach 2 of 3

Top-Down Memoization on (i, j)

TimeO(n²)SpaceO(n²)

The fix once you name the overlap — 'cache solve(i, j) so each window is computed once'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

solve(i, j) returns the same value every call. Where can you store it so each window is computed once?

2Hint 2Explore hint

Use a 2-D memo of size n × n indexed by the window endpoints. Check on entry, fill before returning; use -1 for 'uncomputed' (real lengths are ≥ 0).

3Hint 3Explore hint

There are O(n²) windows and each does O(1) work → O(n²) time and space.

A · Core idea

Keep the end-matching recurrence but cache solve(i, j) in a 2-D table so each window is solved once.

The mental shift: a window's LPS depends only on its endpoints. However you arrived at [i, j], the longest palindromic subsequence inside it is a fixed number. Caching by (i, j) removes all the duplicated work. There are O(n²) windows and each costs O(1) to resolve given its sub-results, so the bound is O(n²) directly.

Choosing the sentinel. Initialise the memo to -1 for 'uncomputed' — real LPS lengths are non-negative, so -1 is unambiguous. The i == j base returns 1 and i > j returns 0 before any lookup.

A language note (Java memo vs Python tabulation). Recursion here nests up to O(n) deep. With n as large as 1000 (the constraint), that depth approaches Python's default recursion limit of about 1000, so a deep, skewed input can overflow the stack. In Java that depth is fine. So in Python you'd either raise the limit with sys.setrecursionlimit or prefer the bottom-up table (next approach), which has no recursion at all. Top-down memoization is the comfortable default in Java; tabulation is the safer default in Python at this size.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "bbbab"

diagonal

memo[i][i] = 1 for all i

Statebase

Final result4

C · Code with teaching comments

Reference implementation previewpublic int longestPalindromeSubseq(String s) { int n = s.length(); int[][] memo = new int[n][n]; for (int[] row : memo) { Arrays.fill(row, -1);Explore the full code

solution.javaJava

Top-Down Memoization on (i, j) — reference

3 teaching notes

1
public int longestPalindromeSubseq(String s) {
2
    int n = s.length();
3
    int[][] memo = new int[n][n];
4
    for (int[] row : memo) {
5
        // -1 marks 'uncomputed'; real LPS lengths are ≥ 0.
6
        Arrays.fill(row, -1);
7
    }
8
    return solve(s, 0, n - 1, memo);
9
}
10
 
11
private int solve(String s, int i, int j, int[][] memo) {
12
    if (i > j) {
13
        return 0;
14
    }
15
    if (i == j) {
16
        return 1;
17
    }
18
    // Cache hit returns the stored window length in O(1).
19
    if (memo[i][j] != -1) {
20
        return memo[i][j];
21
    }
22
    int ans;
23
    if (s.charAt(i) == s.charAt(j)) {
24
        // Matching ends add 2 and recurse on the cached inner window.
25
        ans = 2 + solve(s, i + 1, j - 1, memo);
26
    } else {
27
        ans = Math.max(solve(s, i + 1, j, memo), solve(s, i, j - 1, memo));
28
    }
29
    memo[i][j] = ans;
30
    return ans;
31
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.31 lines

D · Why it works and complexityO(n²) timeO(n²) spaceOpen the invariant and proofExplore the proof

Same mechanical upgrade: a correct recurrence plus a cache keyed on the interval (i, j). The insight — pair matching ends, otherwise drop one — was found in the brute force; memoization is bookkeeping.

ComplexityO(n²) time, O(n²) space — There are O(n²) distinct (i, j) windows; each combines its sub-results in O(1) → O(n²) time. The memo is O(n²); recursion depth is O(n) on top.

E · Edge cases and pitfalls5n near 1000, skewed — Java memo is fine; Python needs a raised limit or the bottom-up table.Explore edge cases

Edge cases handled

n near 1000, skewedJava memo is fine; Python needs a raised limit or the bottom-up table.
no repeats (e.g. "abc")Ends never match → answer 1.

Pitfalls

Using 0 as the sentinel — 0 is a valid length for empty windows; use -1.
Recursing in Python at n ≈ 1000 without raising the limit — risks a stack overflow.
Caching only on one index — both endpoints define the window.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — Interval DP by Increasing Length (Optimal)

TimeO(n²)SpaceO(n) with a rolling row

The answer they want. Frame it as 'fill dp[i][j] so the inner window [i+1][j-1] is ready', and mention the LCS(s, reverse) alternative.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

dp[i][j] = LPS of s[i..j] needs dp[i+1][j-1], dp[i+1][j], and dp[i][j-1] — all on shorter or inner windows. Fill so those are ready first.

2Hint 2Explore hint

Set dp[i][i] = 1. Then fill by increasing window length (or iterate i from n-1 down to 0 and j from i+1 up to n-1).

3Hint 3Explore hint

If s[i]==s[j]: dp[i][j] = 2 + dp[i+1][j-1]; else max(dp[i+1][j], dp[i][j-1]). Answer dp[0][n-1].

A · Core idea

Build dp[i][j] = LPS of s[i..j] so that every window's dependencies are finalised before it. Seed the diagonal dp[i][i] = 1. Then for each window length from 2 to n, set i, compute j = i + length - 1, and apply the recurrence; the answer is dp[0][n-1].

The dependency order. dp[i][j] reads dp[i+1][j-1] (inner window, two shorter), dp[i+1][j] and dp[i][j-1] (one shorter each). All are strictly shorter intervals, so filling by increasing length guarantees they're ready. Equivalently, iterate i from n-1 down to 0 (outer) and j from i+1 up to n-1 (inner) — this also visits [i+1][*] before [i][*]. Either ordering avoids reading an unfilled cell.

The recurrence in table terms. If s[i] == s[j], the two ends pair up: dp[i][j] = 2 + dp[i+1][j-1]. Otherwise drop one end: dp[i][j] = max(dp[i+1][j], dp[i][j-1]). The diagonal of 1s anchors everything, exactly like the single-matrix base in Matrix Chain.

The reverse-LCS reduction. A palindromic subsequence of s reads identically in s and in reverse(s), so the longest one is precisely the Longest Common Subsequence of s and reverse(s). If you already have an LCS routine, LPS(s) = LCS(s, reverse(s)) is a two-line solution with the same O(n²) cost. Mention both framings — the interval DP shows you understand the structure; the reduction shows breadth.

Space compression. Because dp[i][*] depends only on dp[i+1][*] and earlier cells in the same row, keep two rows for O(n) space.

Why bottom-up here. With n up to 1000, the table fill has no recursion, so it sidesteps Python's stack-depth limit entirely — the practical reason to prefer it in Python.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "cbbd"

Interactive diagram

Window dependencies in the LPS table

length 1

Active call / nodeSupporting contextReturned stateNot active

dp[i][j] reads the inner window [i+1][j-1] when ends match, or the one-shorter windows [i+1][j] / [i][j-1] when they differ. Fill by increasing length.

Final result2

C · Code with teaching comments

solution.javaJava

Bottom-Up — Interval DP by Increasing Length (Optimal) — optimal

4 teaching notes

1
public int longestPalindromeSubseq(String s) {
2
    int n = s.length();
3
    int[][] dp = new int[n][n];
4
    for (int i = 0; i < n; i++) {
5
        // Single-character windows are palindromes of length 1 — the diagonal base.
6
        dp[i][i] = 1;
7
    }
8
    // Fill by increasing window length so [i+1][j-1] is already done.
9
    for (int len = 2; len <= n; len++) {
10
        for (int i = 0; i + len - 1 < n; i++) {
11
            int j = i + len - 1;
12
            if (s.charAt(i) == s.charAt(j)) {
13
                // Matching ends pair up: add 2 to the inner window's LPS.
14
                dp[i][j] = 2 + dp[i + 1][j - 1];
15
            } else {
16
                // Differing ends: keep the better of dropping the left or right end.
17
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
18
            }
19
        }
20
    }
21
    return dp[0][n - 1];
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n²) timeO(n) with a rolling row spaceOpen the invariant and proofExplore the proof

This is the 'match the two ends' interval-DP template: state = window [i, j], decision = pair the ends or shrink from one side, fill order = increasing length. The same dp answers Minimum Insertions to make a palindrome (= n − LPS). And the reverse-LCS view connects it to the whole LCS family.

ComplexityO(n²) time, O(n) with a rolling row space — There are O(n²) windows, each filled in O(1) → O(n²) time. The full table is O(n²); since each row depends only on the row below, two rolling rows give O(n) space.

E · Edge cases and pitfalls6single character — Length loop skipped; dp[0][0] = 1.Explore edge cases

Edge cases handled

single characterLength loop skipped; dp[0][0] = 1.
all identical (e.g. "aaaa")Every end pair matches → dp[0][n-1] = n.
already a palindromeThe recurrence pairs every symmetric pair → returns n.

Pitfalls

Iterating i, j in plain ascending order — reads dp[i+1][j-1] before it's filled.
Using max() instead of 2 + inner when the ends match — undercounts the guaranteed pair.
Confusing this with the substring version, which forbids deletions and needs a different DP.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = 1;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Subsequence vs substring

Subsequence allows deletions; substring requires contiguity. On 'bbbab' the subsequence answer is 4 ('bbbb') but the longest palindromic substring is 'bbb' (length 3). Using the substring DP here undercounts.

Explore the code comparison

Don't write this

# expand-around-center finds the longest contiguous palindrome
for center in range(n):
    expand(center)  # WRONG model for subsequence

Write this instead

# interval DP allowing skips
if s[i] == s[j]:
    dp[i][j] = 2 + dp[i + 1][j - 1]
else:
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

max() on matching ends

When s[i]==s[j] both characters are guaranteed to extend the palindrome, so the answer is 2 + inner. Taking max(dp[i+1][j], dp[i][j-1]) ignores that pair and can return a smaller value.

Explore the code comparison

Don't write this

if (s.charAt(i) == s.charAt(j)) {
    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // throws away the pair
}

Write this instead

if (s.charAt(i) == s.charAt(j)) {
    dp[i][j] = 2 + dp[i + 1][j - 1];
}

Wrong fill order

dp[i][j] depends on dp[i+1][j-1] (inner, two shorter). Iterating i ascending and j ascending visits dp[i][j] before dp[i+1][...] exists. Fill by increasing length, or i descending with j ascending.

Explore the code comparison

Don't write this

for i in range(n):
    for j in range(i + 1, n):   # dp[i+1][...] not ready yet
        ...

Write this instead

for length in range(2, n + 1):
    for i in range(0, n - length + 1):
        j = i + length - 1
        ...

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Interval DP on [i, j] — match the two ends or drop one of them

Code pattern to memorize

dp[i][i] = 1
if s[i] == s[j]: dp[i][j] = 2 + dp[i+1][j-1]
else:            dp[i][j] = max(dp[i+1][j], dp[i][j-1])
answer = dp[0][n-1]
# alt: LPS(s) == LCS(s, reverse(s))

Rules to remember

1Subsequence, not substring — you may delete characters but not reorder them, so the picks needn't be contiguous.
2When the two ends match, they both join the palindrome: dp[i][j] = 2 + dp[i+1][j-1].
3When the ends differ, drop one end and take the better side: max(dp[i+1][j], dp[i][j-1]).
4Base case is a single character (dp[i][i] = 1); an empty interval contributes 0.
5Fill by increasing interval length (or iterate i downward, j upward) so the inner interval [i+1, j-1] is ready first.

Use this pattern when

Longest palindromic structure where you may skip characters (subsequence, not substring)
Minimum insertions/deletions to make a string a palindrome (n − LPS)
Any 'match the two ends or shrink from one side' interval problem on a single string
Reductions to LCS where the second string is the reverse of the first

Choose another pattern when

You need a CONTIGUOUS palindrome → Longest Palindromic Substring (expand-around-center or different DP)
You need the actual subsequence string → reconstruct from the table, still O(n²)
Counting distinct palindromic subsequences → a different, harder DP with inclusion-exclusion
n is huge (millions) → O(n²) too slow; the problem usually caps n at a few thousand

Interview takeaway

Longest Palindromic Subsequence is the 'match the ends' interval DP. If the boundary characters agree they both join the palindrome and you recurse inward; if not, you discard one boundary and keep the better side. Equivalently it's LCS(s, reverse(s)). The same dp drives minimum insertions to form a palindrome — that answer is just n minus the LPS.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical 'match the two ends' interval DP on a single string. Recognise it when the state is a window [i, j] and you either pair the boundary characters (when equal) or shrink from one side (when not). Fill by increasing length. Equivalently it's LCS(s, reverse(s)), and n − LPS gives the minimum insertions to form a palindrome.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Longest Palindromic Substring
Contiguous version — expand around each center or use a substring DP; deletions are not allowed.
Minimum Insertions to Make a Palindrome
Coming soon
Answer is n − LPS(s) — the characters not in the longest palindromic subsequence each need a mirror inserted.
Longest Common Subsequence
LPS(s) = LCS(s, reverse(s)) — the same O(n²) grid DP under the hood.
Count Different Palindromic Subsequences
Coming soon
Count distinct palindromic subsequences — a harder interval DP with inclusion–exclusion on repeated characters.

Same pattern

←

Count Paths in a Grid with Obstacles

Continue · Next problem

Wildcard Matching

mediumDynamic ProgrammingLC #516Frequently asked

Longest Palindromic Subsequence

LCPractice

Dynamic Programming · 29 of 44 · 12 min

Given a string s, find the length of the **longest palindromic subsequence** in s.

A subsequence is a sequence derived from s by deleting zero or more characters without changing the order of the remaining characters. A palindrome reads the same forwards and backwards.

Return the length of the longest such subsequence (you do not need to return the subsequence itself).

In plain English

Examples

Example 1

Input: s = "bbbab"
Output: 4
Note: The subsequence 'bbbb' (indices 0,1,2,4) is a palindrome of length 4. You can't reach 5 because of the single 'a'.

Example 2

Input: s = "cbbd"
Output: 2
Note: 'bb' is the longest palindromic subsequence.

Example 3

Input: s = "agbdba"
Output: 5
Note: 'abdba' (drop the 'g') is a palindrome of length 5.

Constraints

1 ≤ s.length ≤ 1000
s consists only of lowercase English letters
The answer is at least 1 (any single character is a palindrome of length 1)
Subsequence (deletions allowed), not substring (contiguous)

Clarifying questions4First question: Subsequence or substring?Explore questions

Q1.Subsequence or substring?
Subsequence — deletions are allowed, the characters needn't be contiguous. 'bbbab' has LPS 4 ('bbbb'), even though those b's aren't adjacent.
Q2.Do I return the length or the actual palindrome?
Just the length here. Reconstructing the subsequence means walking the DP table backward from dp[0][n-1].
Q3.Is the empty string possible?
Constraints say length ≥ 1, so the answer is at least 1. An empty interval would contribute 0 in the recurrence.
Q4.Is there a slick reduction?
Yes — the LPS of s equals the LCS of s and reverse(s). Same O(n²) cost, sometimes easier to code if you already have an LCS routine.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise an interval DP on [i, j], handle the two cases (ends equal → +2 and shrink both; ends differ → drop one end), and can connect it to LCS of s and its reverse.

Where candidates slip

Solving Longest Palindromic SUBSTRING by mistake, using max() when the ends match instead of adding 2, or filling the table in an order where [i+1][j-1] isn't ready yet.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion Matching the Two Ends	`O(2ⁿ)`	`O(n)`	Say this first to establish the two-case interval recurrence (ends match vs differ), then flag the exponential overlap.	Read
2	Top-Down Memoization on (i, j)	`O(n²)`	`O(n²)`	The fix once you name the overlap — 'cache solve(i, j) so each window is computed once'.	Read
3	Bottom-Up — Interval DP by Increasing Length (Optimal)Optimal	`O(n²)`	`O(n) with a rolling row`	The answer they want. Frame it as 'fill dp[i][j] so the inner window [i+1][j-1] is ready', and mention the LCS(s, reverse) alternative.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion Matching the Two Ends

TimeO(2ⁿ)SpaceO(n)

Say this first to establish the two-case interval recurrence (ends match vs differ), then flag the exponential overlap.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at the two ends of the current window s[i..j]. If s[i] == s[j], can both characters be part of the same palindrome? What's left to solve?

2Hint 2Explore hint

If the ends match, they wrap a palindrome: count 2 and recurse on the inner window [i+1, j-1]. If they differ, at least one end is useless — drop one side.

3Hint 3Explore hint

When the ends differ, try both: solve(i+1, j) and solve(i, j-1), and take the max. Base cases: i > j → 0, i == j → 1.

A · Core idea

Define solve(i, j) = length of the longest palindromic subsequence of the window s[i..j].

If i > j the window is empty → 0.
If i == j it's a single character, itself a palindrome → 1.
If s[i] == s[j], both ends can serve as the outer pair of a palindrome, contributing 2, and the rest comes from the inner window: 2 + solve(i+1, j-1).
Otherwise the ends differ; at least one of them cannot be an outer matched character, so drop one and take the better side: max(solve(i+1, j), solve(i, j-1)).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "bab"

solve(0,2): s[0]='b'==s[2]='b'

2 + solve(1,1)

Stateends matched

Final result3

C · Code with teaching comments

Reference implementation previewpublic int longestPalindromeSubseq(String s) { return solve(s, 0, s.length() - 1); } // LPS length of s[i..j]Explore the full code

solution.javaJava

Brute Force — Recursion Matching the Two Ends — reference

3 teaching notes

1
public int longestPalindromeSubseq(String s) {
2
    return solve(s, 0, s.length() - 1);
3
}
4
 
5
// LPS length of s[i..j]
6
private int solve(String s, int i, int j) {
7
    if (i > j) {
8
        return 0;
9
    }
10
    // A single character is a palindrome of length 1 — the diagonal base case.
11
    if (i == j) {
12
        return 1;
13
    }
14
    if (s.charAt(i) == s.charAt(j)) {
15
        // Matching ends both join the palindrome — add 2 and shrink the window on both
16
        // sides.
17
        return 2 + solve(s, i + 1, j - 1);
18
    }
19
    // Differing ends: drop the left or the right end, keep the better side.
20
    return Math.max(solve(s, i + 1, j), solve(s, i, j - 1));
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(2ⁿ) time, O(n) space — When the ends differ the recursion forks into two overlapping subproblems; the unmemoized tree is exponential. Recursion depth is O(n).

E · Edge cases and pitfalls5single character — i == j → 1.Explore edge cases

Edge cases handled

single characteri == j → 1.
all identical charactersEvery end pair matches, recursing straight inward → returns n.

Pitfalls

Using max() when the ends match instead of adding 2 — silently undercounts.
Forgetting the i > j empty-window base case — infinite recursion or wrong counts on even-length matches.
Skipping this approach — verbalising the end-matching recurrence is what the interviewer wants.

03.2

Approach 2 of 3

Top-Down Memoization on (i, j)

TimeO(n²)SpaceO(n²)

The fix once you name the overlap — 'cache solve(i, j) so each window is computed once'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

solve(i, j) returns the same value every call. Where can you store it so each window is computed once?

2Hint 2Explore hint

Use a 2-D memo of size n × n indexed by the window endpoints. Check on entry, fill before returning; use -1 for 'uncomputed' (real lengths are ≥ 0).

3Hint 3Explore hint

There are O(n²) windows and each does O(1) work → O(n²) time and space.

A · Core idea

Keep the end-matching recurrence but cache solve(i, j) in a 2-D table so each window is solved once.

Choosing the sentinel. Initialise the memo to -1 for 'uncomputed' — real LPS lengths are non-negative, so -1 is unambiguous. The i == j base returns 1 and i > j returns 0 before any lookup.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "bbbab"

diagonal

memo[i][i] = 1 for all i

Statebase

Final result4

C · Code with teaching comments

Reference implementation previewpublic int longestPalindromeSubseq(String s) { int n = s.length(); int[][] memo = new int[n][n]; for (int[] row : memo) { Arrays.fill(row, -1);Explore the full code

solution.javaJava

Top-Down Memoization on (i, j) — reference

3 teaching notes

1
public int longestPalindromeSubseq(String s) {
2
    int n = s.length();
3
    int[][] memo = new int[n][n];
4
    for (int[] row : memo) {
5
        // -1 marks 'uncomputed'; real LPS lengths are ≥ 0.
6
        Arrays.fill(row, -1);
7
    }
8
    return solve(s, 0, n - 1, memo);
9
}
10
 
11
private int solve(String s, int i, int j, int[][] memo) {
12
    if (i > j) {
13
        return 0;
14
    }
15
    if (i == j) {
16
        return 1;
17
    }
18
    // Cache hit returns the stored window length in O(1).
19
    if (memo[i][j] != -1) {
20
        return memo[i][j];
21
    }
22
    int ans;
23
    if (s.charAt(i) == s.charAt(j)) {
24
        // Matching ends add 2 and recurse on the cached inner window.
25
        ans = 2 + solve(s, i + 1, j - 1, memo);
26
    } else {
27
        ans = Math.max(solve(s, i + 1, j, memo), solve(s, i, j - 1, memo));
28
    }
29
    memo[i][j] = ans;
30
    return ans;
31
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.31 lines

D · Why it works and complexityO(n²) timeO(n²) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(n²) space — There are O(n²) distinct (i, j) windows; each combines its sub-results in O(1) → O(n²) time. The memo is O(n²); recursion depth is O(n) on top.

E · Edge cases and pitfalls5n near 1000, skewed — Java memo is fine; Python needs a raised limit or the bottom-up table.Explore edge cases

Edge cases handled

n near 1000, skewedJava memo is fine; Python needs a raised limit or the bottom-up table.
no repeats (e.g. "abc")Ends never match → answer 1.

Pitfalls

Using 0 as the sentinel — 0 is a valid length for empty windows; use -1.
Recursing in Python at n ≈ 1000 without raising the limit — risks a stack overflow.
Caching only on one index — both endpoints define the window.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — Interval DP by Increasing Length (Optimal)

TimeO(n²)SpaceO(n) with a rolling row

The answer they want. Frame it as 'fill dp[i][j] so the inner window [i+1][j-1] is ready', and mention the LCS(s, reverse) alternative.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

dp[i][j] = LPS of s[i..j] needs dp[i+1][j-1], dp[i+1][j], and dp[i][j-1] — all on shorter or inner windows. Fill so those are ready first.

2Hint 2Explore hint

Set dp[i][i] = 1. Then fill by increasing window length (or iterate i from n-1 down to 0 and j from i+1 up to n-1).

3Hint 3Explore hint

If s[i]==s[j]: dp[i][j] = 2 + dp[i+1][j-1]; else max(dp[i+1][j], dp[i][j-1]). Answer dp[0][n-1].

A · Core idea

Space compression. Because dp[i][*] depends only on dp[i+1][*] and earlier cells in the same row, keep two rows for O(n) space.

Why bottom-up here. With n up to 1000, the table fill has no recursion, so it sidesteps Python's stack-depth limit entirely — the practical reason to prefer it in Python.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "cbbd"

Interactive diagram

Window dependencies in the LPS table

length 1

Active call / nodeSupporting contextReturned stateNot active

dp[i][j] reads the inner window [i+1][j-1] when ends match, or the one-shorter windows [i+1][j] / [i][j-1] when they differ. Fill by increasing length.

Final result2

C · Code with teaching comments

solution.javaJava

Bottom-Up — Interval DP by Increasing Length (Optimal) — optimal

4 teaching notes

1
public int longestPalindromeSubseq(String s) {
2
    int n = s.length();
3
    int[][] dp = new int[n][n];
4
    for (int i = 0; i < n; i++) {
5
        // Single-character windows are palindromes of length 1 — the diagonal base.
6
        dp[i][i] = 1;
7
    }
8
    // Fill by increasing window length so [i+1][j-1] is already done.
9
    for (int len = 2; len <= n; len++) {
10
        for (int i = 0; i + len - 1 < n; i++) {
11
            int j = i + len - 1;
12
            if (s.charAt(i) == s.charAt(j)) {
13
                // Matching ends pair up: add 2 to the inner window's LPS.
14
                dp[i][j] = 2 + dp[i + 1][j - 1];
15
            } else {
16
                // Differing ends: keep the better of dropping the left or right end.
17
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
18
            }
19
        }
20
    }
21
    return dp[0][n - 1];
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n²) timeO(n) with a rolling row spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6single character — Length loop skipped; dp[0][0] = 1.Explore edge cases

Edge cases handled

single characterLength loop skipped; dp[0][0] = 1.
all identical (e.g. "aaaa")Every end pair matches → dp[0][n-1] = n.
already a palindromeThe recurrence pairs every symmetric pair → returns n.

Pitfalls

Iterating i, j in plain ascending order — reads dp[i+1][j-1] before it's filled.
Using max() instead of 2 + inner when the ends match — undercounts the guaranteed pair.
Confusing this with the substring version, which forbids deletions and needs a different DP.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = 1;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Subsequence vs substring

Explore the code comparison

Don't write this

# expand-around-center finds the longest contiguous palindrome
for center in range(n):
    expand(center)  # WRONG model for subsequence

Write this instead

# interval DP allowing skips
if s[i] == s[j]:
    dp[i][j] = 2 + dp[i + 1][j - 1]
else:
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

max() on matching ends

When s[i]==s[j] both characters are guaranteed to extend the palindrome, so the answer is 2 + inner. Taking max(dp[i+1][j], dp[i][j-1]) ignores that pair and can return a smaller value.

Explore the code comparison

Don't write this

if (s.charAt(i) == s.charAt(j)) {
    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // throws away the pair
}

Write this instead

if (s.charAt(i) == s.charAt(j)) {
    dp[i][j] = 2 + dp[i + 1][j - 1];
}

Wrong fill order

dp[i][j] depends on dp[i+1][j-1] (inner, two shorter). Iterating i ascending and j ascending visits dp[i][j] before dp[i+1][...] exists. Fill by increasing length, or i descending with j ascending.

Explore the code comparison

Don't write this

for i in range(n):
    for j in range(i + 1, n):   # dp[i+1][...] not ready yet
        ...

Write this instead

for length in range(2, n + 1):
    for i in range(0, n - length + 1):
        j = i + length - 1
        ...

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Interval DP on [i, j] — match the two ends or drop one of them

Code pattern to memorize

dp[i][i] = 1
if s[i] == s[j]: dp[i][j] = 2 + dp[i+1][j-1]
else:            dp[i][j] = max(dp[i+1][j], dp[i][j-1])
answer = dp[0][n-1]
# alt: LPS(s) == LCS(s, reverse(s))

Rules to remember

1Subsequence, not substring — you may delete characters but not reorder them, so the picks needn't be contiguous.
2When the two ends match, they both join the palindrome: dp[i][j] = 2 + dp[i+1][j-1].
3When the ends differ, drop one end and take the better side: max(dp[i+1][j], dp[i][j-1]).
4Base case is a single character (dp[i][i] = 1); an empty interval contributes 0.
5Fill by increasing interval length (or iterate i downward, j upward) so the inner interval [i+1, j-1] is ready first.

Use this pattern when

Longest palindromic structure where you may skip characters (subsequence, not substring)
Minimum insertions/deletions to make a string a palindrome (n − LPS)
Any 'match the two ends or shrink from one side' interval problem on a single string
Reductions to LCS where the second string is the reverse of the first

Choose another pattern when

You need a CONTIGUOUS palindrome → Longest Palindromic Substring (expand-around-center or different DP)
You need the actual subsequence string → reconstruct from the table, still O(n²)
Counting distinct palindromic subsequences → a different, harder DP with inclusion-exclusion
n is huge (millions) → O(n²) too slow; the problem usually caps n at a few thousand

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Longest Palindromic Substring
Contiguous version — expand around each center or use a substring DP; deletions are not allowed.
Minimum Insertions to Make a Palindrome
Coming soon
Answer is n − LPS(s) — the characters not in the longest palindromic subsequence each need a mirror inserted.
Longest Common Subsequence
LPS(s) = LCS(s, reverse(s)) — the same O(n²) grid DP under the hood.
Count Different Palindromic Subsequences
Coming soon
Count distinct palindromic subsequences — a harder interval DP with inclusion–exclusion on repeated characters.

Same pattern

←

Count Paths in a Grid with Obstacles

Continue · Next problem

Wildcard Matching