Longest Palindromic Subsequence (LeetCode 516)
Given a string s, find the length of its longest palindromic subsequence. A subsequence keeps the letters of s in their original order but may skip any of them, so its letters do not have to sit next to each other. A palindrome reads the same from left to right and from right to left.
For example, the letters at positions 0, 1, 2 and 4 of "bbbab" form "bbbb", a palindrome of length 4, and no palindromic subsequence of that string is longer.
Return only the length, not the subsequence itself.
Worked Examples
s = "bbbab"4"bbbb". The a at position 3 is skipped.s = "cbbd"2"bb" is the longest palindromic subsequence. The c and the d are skipped.⚖️Formal Constraints & Bounds
1 <= s.length <= 1000sconsists only of lowercase English letters.
Core Insight
Look at the two end letters of a range: when they match they wrap the best palindrome inside, and when they differ one of them is dropped, so every range is answered from shorter ranges inside it.
Real-World Scenario & Production Applications
Any question about the longest symmetric pattern that hides in a sequence with noise in between: the symmetric core of a DNA strand, the longest mirrored run in a log of events, or how far a text is from being a palindrome (the fewest letters to delete).
Step-by-Step Execution Trace Table
Trace of Example 1: s = "bbbab", so n = 5 and every one-letter range dp[i][i] starts at 1. Each row is one range (i, j), filled by increasing length.
length | Range (i, j) | How the cell is built | dp[i][j] |
|---|---|---|---|
| 2 | (0, 1) bb | b = b: nothing inside, 0 + 2 | 2 |
| 2 | (1, 2) bb | b = b: nothing inside, 0 + 2 | 2 |
| 2 | (2, 3) ba | b != a: max(dp[3][3], dp[2][2]) = max(1, 1) | 1 |
| 2 | (3, 4) ab | a != b: max(dp[4][4], dp[3][3]) = max(1, 1) | 1 |
| 3 | (0, 2) bbb | b = b: dp[1][1] + 2 = 1 + 2 | 3 |
| 3 | (1, 3) bba | b != a: max(dp[2][3], dp[1][2]) = max(1, 2) | 2 |
| 3 | (2, 4) bab | b = b: dp[3][3] + 2 = 1 + 2 | 3 |
| 4 | (0, 3) bbba | b != a: max(dp[1][3], dp[0][2]) = max(2, 3) | 3 |
| 4 | (1, 4) bbab | b = b: dp[2][3] + 2 = 1 + 2 | 3 |
| 5 | (0, 4) bbbab | b = b: dp[1][3] + 2 = 2 + 2 | 4 |
The last range (0, 4) has equal end letters, so it wraps the answer for (1, 3) and adds 2. Reading dp[1][3] there only works because the length loop filled it one pass earlier.
| 1 | `dp[i][j]` is the length of the longest palindromic subsequence of the range `s[i..j]`; `dp[i][i] = 1`. |
| 2 | Fill by `length` from `2` up, so every shorter range is final before it is read. |
| 3 | Equal end letters give `dp[i + 1][j - 1] + 2`; different end letters give `max(dp[i + 1][j], dp[i][j - 1])`. |
| 4 | Return `dp[0][n - 1]`. The trap: filling row by row from `i = 0` reads `dp[i + 1][j - 1]` while it is still `0`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A palindromic subsequence keeps letters in order but may skip letters, so a question about the whole string splits into questions about smaller ranges inside it. Interval DP gives every range s[i..j] one answer, dp[i][j], and builds it from the ranges inside it: look at the two end letters, and either they match and wrap the inside range, or one of them is dropped.
🪞 The Analogy: Closing a Pair of Brackets
Think of the two ends of the range as a pair of brackets you may only close when both letters are equal. If they are equal, close the pair and solve the range inside. If they differ, at least one letter is not part of the answer, so you try the range without the left letter and the range without the right letter, and keep the better one.
🔑 The Key Idea in the Code
dp[i + 1][j - 1], dp[i + 1][j] and dp[i][j - 1] are all shorter ranges, so the length loop has already made them final before dp[i][j] reads them. Filling row by row from i = 0 would read cells that are still 0.
Filling row by row from
i = 0:dp[i][j]readsdp[i + 1][j - 1]anddp[i + 1][j], which belong to rows further down the table. Fill bylength, short ranges first, so those cells are final when they are read.Forgetting the one-letter base:
dp[i][i] = 1, because one letter is already a palindrome. With a base of 0, every answer is too small by the letters that match nothing else.Dropping both ends on a mismatch: when
s[i] != s[j], the answer ismax(dp[i + 1][j], dp[i][j - 1]), notdp[i + 1][j - 1]. Dropping both letters throws away a letter that may still be part of the answer.Mixing up substring and subsequence: a subsequence may skip letters, so the answer is built from the ranges with one end dropped, not from the range that must stay unbroken.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Longest palindromic subsequence": the letters keep their order but may be skipped, so a question about the whole string splits into questions about the ranges inside it. A question about one stretch of a sequence whose answer comes from smaller stretches points to Interval DP.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
dp[i][j] is the length of the longest palindromic subsequence of s[i..j]. Equal end letters give dp[i][j] = dp[i + 1][j - 1] + 2; different end letters give dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]). Every one-letter range is 1, and every cell reads only shorter ranges.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Fill order:
dp[i][j]readsdp[i + 1][j - 1]anddp[i + 1][j], rows further down the table. Loopingiupward row by row reads them while they are still0: on"bbbab"the answer comes out2instead of4. Loopfor length in range(2, n + 1)outermost.Base:
dp[i][i] = 1. With0, a string whose letters all differ answers0instead of1.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Interval DP. Let dp of i, j be the length of the longest palindromic subsequence of the letters from i to j. A range of one letter is a palindrome of length one. For a longer range I look at its two end letters: if they match, they wrap the best answer for the range inside them, so I add two to dp of i plus one, j minus one; if they differ, one of them cannot be used, so I take the better of dropping the left end or the right end. Every cell reads only shorter ranges, so I fill by increasing length and return dp of zero, n minus one. That is order N squared time and order N squared space.
Complexity & Mathematical Proof
O(N^2)
Look at the two loops. With n = len(s), length runs from 2 to n, and for each length, i takes n - length + 1 values, so every range (i, j) with i < j is visited exactly once: about n^2 / 2 ranges. The body compares two letters and reads at most two finished cells, so each range costs O(1). Time is O(N^2).
O(N^2)
dp is an n x n table: O(N^2). The loops keep only a few integers (length, i, j) and there is no recursion, so the table dominates. If only the length is needed, two rows are enough, but the standard solution keeps the table.
Derivation Progression
for length and for i visit every range (i, j) with at least two letters exactly once.
O(1)
if s[i] == s[j] compares two letters, and the update reads at most two finished cells: no loop inside.
One constant-time update for each of about N^2 / 2 ranges.
Variable Definitions
Number of letters, len(s)
j - i + 1, the number of letters in a range
Length of the longest palindromic subsequence of s[i..j]
Memory Architecture & Bounds
O(1): two nested loops, no recursion
O(N^2): the table dp with N x N cells
O(1): one integer
Boundary Best / Worst Cases
: the loops never stop early, so every input of length N fills the same N^2 / 2 cells.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "longest palindromic subsequence", "skip letters but keep their order". The answer for a stretch of the string comes from the answers for shorter stretches inside it, so this is Interval DP: look at the two end letters of the range (i, j).
letters, so the table has cells and the loops visit ranges: well within budget. The answer is at most , so it fits any integer type. Checking every subsequence would be .
At scale, the table is the memory cost: for a string of letters it would not fit. If only the length is needed, running i from n - 1 down to 0 needs only row i + 1 at a time ( memory), but then the subsequence itself cannot be rebuilt.
Longest Palindromic Subsequence (LeetCode 516)
Given a string s, find the length of its longest palindromic subsequence. A subsequence keeps the letters of s in their original order but may skip any of them, so its letters do not have to sit next to each other. A palindrome reads the same from left to right and from right to left.
For example, the letters at positions 0, 1, 2 and 4 of "bbbab" form "bbbb", a palindrome of length 4, and no palindromic subsequence of that string is longer.
Return only the length, not the subsequence itself.
Worked Examples
s = "bbbab"4"bbbb". The a at position 3 is skipped.s = "cbbd"2"bb" is the longest palindromic subsequence. The c and the d are skipped.⚖️Formal Constraints & Bounds
1 <= s.length <= 1000sconsists only of lowercase English letters.
Core Insight
Look at the two end letters of a range: when they match they wrap the best palindrome inside, and when they differ one of them is dropped, so every range is answered from shorter ranges inside it.
Real-World Scenario & Production Applications
Any question about the longest symmetric pattern that hides in a sequence with noise in between: the symmetric core of a DNA strand, the longest mirrored run in a log of events, or how far a text is from being a palindrome (the fewest letters to delete).
Step-by-Step Execution Trace Table
Trace of Example 1: s = "bbbab", so n = 5 and every one-letter range dp[i][i] starts at 1. Each row is one range (i, j), filled by increasing length.
length | Range (i, j) | How the cell is built | dp[i][j] |
|---|---|---|---|
| 2 | (0, 1) bb | b = b: nothing inside, 0 + 2 | 2 |
| 2 | (1, 2) bb | b = b: nothing inside, 0 + 2 | 2 |
| 2 | (2, 3) ba | b != a: max(dp[3][3], dp[2][2]) = max(1, 1) | 1 |
| 2 | (3, 4) ab | a != b: max(dp[4][4], dp[3][3]) = max(1, 1) | 1 |
| 3 | (0, 2) bbb | b = b: dp[1][1] + 2 = 1 + 2 | 3 |
| 3 | (1, 3) bba | b != a: max(dp[2][3], dp[1][2]) = max(1, 2) | 2 |
| 3 | (2, 4) bab | b = b: dp[3][3] + 2 = 1 + 2 | 3 |
| 4 | (0, 3) bbba | b != a: max(dp[1][3], dp[0][2]) = max(2, 3) | 3 |
| 4 | (1, 4) bbab | b = b: dp[2][3] + 2 = 1 + 2 | 3 |
| 5 | (0, 4) bbbab | b = b: dp[1][3] + 2 = 2 + 2 | 4 |
The last range (0, 4) has equal end letters, so it wraps the answer for (1, 3) and adds 2. Reading dp[1][3] there only works because the length loop filled it one pass earlier.
| 1 | `dp[i][j]` is the length of the longest palindromic subsequence of the range `s[i..j]`; `dp[i][i] = 1`. |
| 2 | Fill by `length` from `2` up, so every shorter range is final before it is read. |
| 3 | Equal end letters give `dp[i + 1][j - 1] + 2`; different end letters give `max(dp[i + 1][j], dp[i][j - 1])`. |
| 4 | Return `dp[0][n - 1]`. The trap: filling row by row from `i = 0` reads `dp[i + 1][j - 1]` while it is still `0`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A palindromic subsequence keeps letters in order but may skip letters, so a question about the whole string splits into questions about smaller ranges inside it. Interval DP gives every range s[i..j] one answer, dp[i][j], and builds it from the ranges inside it: look at the two end letters, and either they match and wrap the inside range, or one of them is dropped.
🪞 The Analogy: Closing a Pair of Brackets
Think of the two ends of the range as a pair of brackets you may only close when both letters are equal. If they are equal, close the pair and solve the range inside. If they differ, at least one letter is not part of the answer, so you try the range without the left letter and the range without the right letter, and keep the better one.
🔑 The Key Idea in the Code
dp[i + 1][j - 1], dp[i + 1][j] and dp[i][j - 1] are all shorter ranges, so the length loop has already made them final before dp[i][j] reads them. Filling row by row from i = 0 would read cells that are still 0.
Filling row by row from
i = 0:dp[i][j]readsdp[i + 1][j - 1]anddp[i + 1][j], which belong to rows further down the table. Fill bylength, short ranges first, so those cells are final when they are read.Forgetting the one-letter base:
dp[i][i] = 1, because one letter is already a palindrome. With a base of 0, every answer is too small by the letters that match nothing else.Dropping both ends on a mismatch: when
s[i] != s[j], the answer ismax(dp[i + 1][j], dp[i][j - 1]), notdp[i + 1][j - 1]. Dropping both letters throws away a letter that may still be part of the answer.Mixing up substring and subsequence: a subsequence may skip letters, so the answer is built from the ranges with one end dropped, not from the range that must stay unbroken.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Longest palindromic subsequence": the letters keep their order but may be skipped, so a question about the whole string splits into questions about the ranges inside it. A question about one stretch of a sequence whose answer comes from smaller stretches points to Interval DP.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
dp[i][j] is the length of the longest palindromic subsequence of s[i..j]. Equal end letters give dp[i][j] = dp[i + 1][j - 1] + 2; different end letters give dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]). Every one-letter range is 1, and every cell reads only shorter ranges.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Fill order:
dp[i][j]readsdp[i + 1][j - 1]anddp[i + 1][j], rows further down the table. Loopingiupward row by row reads them while they are still0: on"bbbab"the answer comes out2instead of4. Loopfor length in range(2, n + 1)outermost.Base:
dp[i][i] = 1. With0, a string whose letters all differ answers0instead of1.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Interval DP. Let dp of i, j be the length of the longest palindromic subsequence of the letters from i to j. A range of one letter is a palindrome of length one. For a longer range I look at its two end letters: if they match, they wrap the best answer for the range inside them, so I add two to dp of i plus one, j minus one; if they differ, one of them cannot be used, so I take the better of dropping the left end or the right end. Every cell reads only shorter ranges, so I fill by increasing length and return dp of zero, n minus one. That is order N squared time and order N squared space.
Complexity & Mathematical Proof
O(N^2)
Look at the two loops. With n = len(s), length runs from 2 to n, and for each length, i takes n - length + 1 values, so every range (i, j) with i < j is visited exactly once: about n^2 / 2 ranges. The body compares two letters and reads at most two finished cells, so each range costs O(1). Time is O(N^2).
O(N^2)
dp is an n x n table: O(N^2). The loops keep only a few integers (length, i, j) and there is no recursion, so the table dominates. If only the length is needed, two rows are enough, but the standard solution keeps the table.
Derivation Progression
for length and for i visit every range (i, j) with at least two letters exactly once.
O(1)
if s[i] == s[j] compares two letters, and the update reads at most two finished cells: no loop inside.
One constant-time update for each of about N^2 / 2 ranges.
Variable Definitions
Number of letters, len(s)
j - i + 1, the number of letters in a range
Length of the longest palindromic subsequence of s[i..j]
Memory Architecture & Bounds
O(1): two nested loops, no recursion
O(N^2): the table dp with N x N cells
O(1): one integer
Boundary Best / Worst Cases
: the loops never stop early, so every input of length N fills the same N^2 / 2 cells.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "longest palindromic subsequence", "skip letters but keep their order". The answer for a stretch of the string comes from the answers for shorter stretches inside it, so this is Interval DP: look at the two end letters of the range (i, j).
letters, so the table has cells and the loops visit ranges: well within budget. The answer is at most , so it fits any integer type. Checking every subsequence would be .
At scale, the table is the memory cost: for a string of letters it would not fit. If only the length is needed, running i from n - 1 down to 0 needs only row i + 1 at a time ( memory), but then the subsequence itself cannot be rebuilt.