Use the longest palindromic subsequence interview answer in 60 seconds: say the recurrence, dry-run bbbab, and explain reconstruction clearly.
Most people who blank on this problem in an interview don't blank because they forgot the algorithm. They blank because they never had a clean spoken version of it — just a half-remembered DP table and the vague memory of a tutorial. The longest palindromic subsequence interview question is one of those problems where you can technically know the answer and still sound completely lost when you have to say it out loud. This article is about fixing that: the 60-second explanation, the recurrence you can derive on the spot, and the one dry run that makes the table feel obvious instead of arbitrary.
What Longest Palindromic Subsequence Means in Interview Terms
Why the interview version is not the textbook version
Candidates who've studied this problem can usually recite something like "it's the length of the longest palindromic subsequence in a string." That definition is correct. It is also nearly useless in an interview, because the moment the interviewer asks "okay, so what does your recurrence look like?" or "walk me through a small example," the memorized definition doesn't give you anything to work with.
The real problem is that most prep resources teach LPS as a table to fill in, not as an idea to understand. So when a candidate sits down with "bbbab" and tries to explain why the answer is 4, they reach for the table and realize they can't reconstruct how it got built — only that it did.
What this looks like in practice
In plain English, the longest palindromic subsequence of a string is the longest sequence of characters from that string — taken in order but not necessarily adjacent — that reads the same forwards and backwards.
For "bbbab": the answer is 4, because "bbbb" is a valid subsequence (pick indices 0, 1, 2, 4) and it's a palindrome. You skip the 'a'. That's the key — you're allowed to skip characters.
According to CLRS and standard algorithm references, a subsequence preserves relative order but does not require contiguity. A substring is contiguous by definition. The longest palindromic substring of "bbbab" is "bbb" — length 3. The longest palindromic subsequence is length 4. That one character of difference comes entirely from the freedom to skip.
In a coaching session I ran with a junior engineer prepping for a mid-level role, the candidate kept saying "subarray" for the first twenty minutes. The definition only clicked when we drew two boxes on the whiteboard: one labeled "must be a block" and one labeled "can have gaps." Once the visual was there, the whole recurrence made sense — because the recurrence is really just asking "what do I do at the gaps?"
Say the 60-Second Answer Before You Try to Prove It
The answer should sound like a person, not a proof dump
When the interviewer asks you to explain the LPS interview question, they are not asking for a lecture. They want to hear that you understand the shape of the problem before you start writing code. The answer that lands is structured, not dense: one sentence for the core idea, one for the recurrence, one for complexity, one for the caveat about subsequence versus substring.
What doesn't work is starting with "so we build a 2D DP table where dp[i][j] represents..." before you've said what you're actually trying to find. That's a proof dump — technically correct, but it tells the interviewer you memorized the solution rather than understood it.
What this looks like in practice
Here's the 60–90 second spoken script that actually works in a live mock:
"The idea is: I want the longest palindromic subsequence in this string. Subsequence means characters in order but not necessarily adjacent — so I can skip characters. The key insight is that I can check the two ends of any window. If they match, they both contribute to the palindrome, so I take 2 plus whatever's inside. If they don't match, I drop one end and try both options, taking the better result. That gives me the recurrence: dp[i][j] = dp[i+1][j-1] + 2 if the ends match, otherwise max(dp[i+1][j], dp[i][j-1]). I fill this bottom-up from short windows to long ones. Time is O(n²), space is O(n²) but reducible to O(n). And one thing worth flagging: this is not the longest palindromic substring — that's a different problem with a different algorithm."
That script runs about 75 seconds at a normal pace. The phrase that made it click in mock sessions was "drop one end and try both options" — it's the moment the recurrence stops sounding like magic and starts sounding like a decision. Before that phrasing, candidates would say "DP table stuff" and wave their hands. After it, they could explain why the max is there.
Stop Mixing Up Subsequence and Substring
The mistake that makes the rest of the answer wobble
Substring intuition is natural. When you hear "longest palindrome in a string," the brain defaults to looking for a contiguous block — because that's what you can see when you read the string left to right. The problem is that substring intuition breaks the algorithm. If you think you need a contiguous block, you'll write a completely different approach (expand-around-center, or Manacher's algorithm), and it won't solve this problem.
The reason DP is needed for longest palindromic subsequence vs substring is exactly the freedom to skip: you have exponentially many possible subsequences, and the only tractable way to find the best one is to decompose the problem into overlapping subproblems.
What this looks like in practice
Take the string "cbbd".
- Longest palindromic substring: "bb" — length 2. That's the longest contiguous palindrome.
- Longest palindromic subsequence: "bb" — also length 2 here, but for "bbbab" the gap widens dramatically: substring gives "bbb" (length 3), subsequence gives "bbbb" (length 4).
A cleaner contrast: take "agbdba".
- Longest palindromic substring: "bdb" — length 3.
- Longest palindromic subsequence: "abdba" — length 5, skipping the 'g'.
That's the difference. The subsequence can reach across gaps the substring can't. According to GeeksforGeeks' algorithm documentation, which cites the standard formulation, the subsequence version is strictly more powerful — and strictly harder to solve.
On a whiteboard, the comparison takes about thirty seconds and it's the single most effective thing you can do to prove you understand the problem statement before you touch the recurrence.
Derive the DP Recurrence Instead of Memorizing It
Why the state has to be a substring boundary pair
The state dp[i][j] represents the length of the longest palindromic subsequence within s[i..j] — the substring from index i to index j, inclusive. The reason the state needs two indices is that the problem shrinks from both ends simultaneously. You're always asking: given this window, what's the best I can do? And the window is defined by two boundaries, not one.
If the state were just a single index, you couldn't express "I've already handled the outer characters and now I'm looking at what's inside." Palindromic subsequence DP is inherently a 2D problem because the subproblem structure is a window, not a prefix or suffix.
What this looks like in practice
Work through "bbbab" step by step.
Start at the ends: s[0] = 'b', s[4] = 'b'. They match. So dp[0][4] = dp[1][3] + 2. Now I need dp[1][3], which is the window "bba". s[1] = 'b', s[3] = 'a'. They don't match. So dp[1][3] = max(dp[2][3], dp[1][2]). dp[2][3] is "ba" — ends don't match, so max(dp[3][3], dp[2][2]) = max(1, 1) = 1. dp[1][2] is "bb" — ends match, so dp[2][1] + 2. But dp[2][1] is an empty window (i > j), which is 0. So dp[1][2] = 2. Back up: dp[1][3] = max(1, 2) = 2. And dp[0][4] = 2 + 2 = 4.
The answer is 4. Every step was a decision: match the ends or drop one side.
The base cases that keep the whole thing from collapsing
Three base cases anchor the recurrence:
Single character (i == j): A single character is trivially a palindrome of length 1. dp[i][i] = 1.
Empty window (i > j): When the window has no characters — which happens when you expand inward past a matched pair — the length is 0. dp[i][j] = 0 for i > j.
Two characters (j == i + 1): If they match, dp[i][j] = 2. If they don't, dp[i][j] = 1. This follows directly from the recurrence but it's worth checking explicitly.
Without these, the recurrence has no floor to stand on. The single-character case is the one students most often forget to initialize, which causes the whole table to read wrong.
Show the Same Idea Two Ways: Memoization and Tabulation
Top-down feels natural until the interviewer asks about repeat work
Memoization is just the recursive recurrence with a cache attached. You write the natural recursion — if ends match, recurse inside; if not, recurse dropping each end and take the max — and you store every result in a 2D memo table so you never compute the same (i, j) pair twice. LPS dynamic programming in top-down form is often easier to write first because it follows the recurrence directly without requiring you to think about fill order.
The problem is that a naive recursive solution without memoization recomputes overlapping subproblems exponentially. With memoization, you get O(n²) time and O(n²) space — same as tabulation.
What this looks like in practice
In the memoized version, the call tree for dp(0, 4) on "bbbab" branches into dp(1, 3), which branches into dp(2, 3) and dp(1, 2). dp(2, 3) eventually calls dp(2, 2) and dp(3, 3) — both base cases. Without memoization, dp(2, 2) gets called multiple times through different branches. With the cache, it's computed once.
In the tabulated version, you fill the same cells but in a deliberate order: all windows of length 1 first (the diagonal), then length 2, then length 3, up to length n. Each cell only depends on cells representing shorter windows, so by the time you compute dp[i][j], dp[i+1][j-1], dp[i+1][j], and dp[i][j-1] are already filled.
The tabulation version the interviewer can follow on a whiteboard
Fill order matters for tabulation. You iterate over window length L from 1 to n, and for each length, iterate over all starting positions i where j = i + L - 1 is still in bounds. This guarantees the dependency chain: shorter windows are always computed before the longer windows that depend on them.
In practice, most candidates who understand memoization can switch to tabulation by just changing the traversal order. According to standard DP complexity analysis, both approaches run in O(n²) time and O(n²) space. Space can be reduced to O(n) by noting that each row only depends on the previous row — but that optimization is worth mentioning only after you've explained the full table.
Dry-Run bbbab Until the Table Stops Being Scary
The table only makes sense once you see one row at a time
The DP table for "bbbab" is a 5×5 grid where dp[i][j] is only meaningful when i ≤ j. The diagonal (i == j) is all 1s — every single character is a palindrome of length 1. Below the diagonal is unused (i > j, so 0 by convention).
The filling proceeds diagonally upward: first the main diagonal (L=1), then the super-diagonal (L=2), then L=3, L=4, and finally L=5 which gives dp[0][4] — the answer.
What this looks like in practice
For "bbbab" (indices 0–4):
- L=1: dp[0][0]=1, dp[1][1]=1, dp[2][2]=1, dp[3][3]=1, dp[4][4]=1.
- L=2: dp[0][1]: s[0]='b', s[1]='b' — match → dp[1][0]+2 = 0+2 = 2. dp[1][2]: 'b','b' — match → 2. dp[2][3]: 'b','a' — no match → max(dp[3][3], dp[2][2]) = max(1,1) = 1. dp[3][4]: 'a','b' — no match → 1.
- L=3: dp[1][3]: 'b','a' — no match → max(dp[2][3], dp[1][2]) = max(1,2) = 2. dp[0][2]: 'b','b' — match → dp[1][1]+2 = 3.
- L=4: dp[0][3]: 'b','a' — no match → max(dp[1][3], dp[0][2]) = max(2,3) = 3. dp[1][4]: 'b','b' — match → dp[2][3]+2 = 1+2 = 3.
- L=5: dp[0][4]: 'b','b' — match → dp[1][3]+2 = 2+2 = 4.
The answer is 4. The cell that students most often compute wrong is dp[0][2] — they forget that 'b' and 'b' match across a gap and that the inside is just dp[1][1]=1, giving 3. Once that cell is right, the rest follows.
Reconstruct One Actual Palindrome, Not Just the Length
Why interviewers ask this after you solve the easy part
Length tells the interviewer you can implement DP. Reconstruction tells them you understand what the table actually encodes — the sequence of decisions that led to the optimal answer. It's a natural follow-up because it separates candidates who filled in a formula from candidates who understand the structure.
What this looks like in practice
Backtracking through the table uses the same logic as the recurrence, in reverse. Start at dp[0][n-1]. At each step:
- If s[i] == s[j]: these two characters are part of the palindrome. Add s[i] to the front and s[j] to the back of your result. Move to dp[i+1][j-1].
- If s[i] != s[j]: check which neighbor was larger. If dp[i+1][j] >= dp[i][j-1], move to (i+1, j). Otherwise move to (i, j-1).
- Stop when i > j (empty window) or i == j (add s[i] to the middle).
For "bbbab": start at dp[0][4]. s[0]='b', s[4]='b' — match. Add 'b' to both ends. Move to dp[1][3]. s[1]='b', s[3]='a' — no match. dp[2][3]=1, dp[1][2]=2 — go to (1,2). s[1]='b', s[2]='b' — match. Add 'b' to both ends. Move to dp[2][1] — empty. Result: "bbbb". That's one valid longest palindromic subsequence.
In coaching sessions, this is consistently where candidates get stuck after giving the correct length — they've never traced backwards through the table and the logic feels inverted. The fix is to remember: you're just replaying the decisions the recurrence made, in reverse order.
Use the LCS Shortcut Without Hiding the Real Idea
Why the shortcut works and why it can mislead you
The shortcut is valid: reverse the string, find the longest common subsequence between the original and the reversed string, and you get the LPS length. For "bbbab", the reverse is "babbb". The LCS of "bbbab" and "babbb" is 4 — which matches.
The reason it works is structural: any palindromic subsequence of s is a common subsequence of s and its reverse, because reading a palindrome backwards gives the same sequence. The longest one corresponds to the LCS.
What this looks like in practice
In practice, I recommend deriving the direct recurrence first in an interview, then mentioning the LCS conversion if the interviewer asks for an alternative approach. The LCS shortcut can make it look like you don't know the original problem — it's a reduction, not an explanation. If an interviewer asks "why does that work?" and you can't connect it back to the palindrome structure, you've traded a clean answer for a clever-looking one.
According to standard algorithm references including CLRS, the LCS formulation is equivalent in time and space complexity: O(n²) time, O(n²) space. The direct recurrence and the LCS reduction are the same idea in different packaging — which is exactly what you should say if the interviewer asks.
Handle the Follow-Ups That Decide Whether You Really Know It
The questions that usually come next
After you explain the recurrence and run through an example, the follow-up questions are predictable. Knowing them in advance is the difference between a strong close and a trailing-off answer.
What this looks like in practice
"Why not a greedy approach?" Greedy fails because there's no local choice that guarantees a global optimum. Choosing the outermost matching characters doesn't tell you anything about what happens in the middle — you need to explore both the match and the drop-one-side cases, which requires the full DP structure.
"What do the indices mean?" dp[i][j] is the length of the longest palindromic subsequence within the substring s[i..j]. The indices are a window boundary, not a position in the final answer.
"How would you optimize space?" The recurrence for dp[i][j] only depends on dp[i+1][j-1], dp[i+1][j], and dp[i][j-1]. You can reduce space to O(n) by keeping only two rows at a time — the current window length and the previous one. The tradeoff is that reconstruction becomes harder without the full table.
"What's the time complexity?" O(n²) for both memoized and tabulated versions. There are O(n) states for each of the O(n) window lengths, and each state takes O(1) to compute given its dependencies.
What to say when you get stuck
The honest recovery line is: "Let me go back to the core idea. I'm looking at the two ends of the window. If they match, they're both in the palindrome and I recurse inside. If they don't, I drop one end and take the better result. Which part would you like me to expand on?" That sentence resets the conversation without signaling panic. It also proves you have a mental anchor — the end-match / drop-one-side idea — that you can return to whenever the explanation drifts.
In coaching, the candidates who recover best are the ones who stop trying to reconstruct the table from memory and instead re-derive it from that single idea. The table is a consequence of the logic. If you have the logic, you can always rebuild the table.
FAQ
Q: What is the fastest way to explain longest palindromic subsequence in an interview?
One sentence for the idea, one for the recurrence, one for complexity, one for the subsequence caveat. "Compare the two ends of the window. If they match, take 2 plus the inside. If not, drop one end and take the max. That's O(n²) time and space, and it only works because subsequence lets you skip characters." That's the whole answer in four sentences.
Q: How do you derive the DP recurrence instead of memorizing it?
Start from the decision at the ends of the window. If s[i] == s[j], both characters contribute, so dp[i][j] = dp[i+1][j-1] + 2. If they don't match, neither can be in the same palindrome, so you try dropping each one: dp[i][j] = max(dp[i+1][j], dp[i][j-1]). The base cases are dp[i][i] = 1 and dp[i][j] = 0 when i > j. Every part of the recurrence follows from the decision, not from memory.
Q: What is the difference between longest palindromic subsequence and longest palindromic substring?
Substring must be contiguous — you can't skip characters. Subsequence only requires relative order — you can skip. For "bbbab", the longest palindromic substring is "bbb" (length 3); the longest palindromic subsequence is "bbbb" (length 4). The algorithms are completely different: substring uses expand-around-center or Manacher's; subsequence uses 2D DP.
Q: Why does the problem use a 2D DP state, and what do the indices mean?
Because the subproblem is a window, not a single position. dp[i][j] is the longest palindromic subsequence within s[i..j]. The problem shrinks from both ends simultaneously, so you need two indices to describe the current window. A single index can't capture "I've already matched the outer characters and now I'm looking at what's inside."
Q: How do you convert the problem to longest common subsequence with the reversed string?
Reverse the string to get s'. The LPS of s equals the LCS of s and s'. Any palindromic subsequence of s is a common subsequence of s and s' (because reading a palindrome backwards gives the same sequence), and the longest one corresponds to the LCS. The complexity is identical: O(n²) time and space.
Q: What are the time and space tradeoffs between recursion, memoization, tabulation, and space optimization?
Naive recursion is O(2^n) time — exponential because of overlapping subproblems. Memoization brings it to O(n²) time and O(n²) space by caching results. Tabulation is also O(n²) time and O(n²) space but avoids recursion overhead. Space-optimized tabulation reduces space to O(n) by keeping only two rows, at the cost of making reconstruction harder.
Q: How do you dry-run the solution on a sample string like bbbab or cbbd?
For "bbbab": fill the DP table diagonally. All single-character windows are 1. For two-character windows: "bb" pairs give 2, mismatched pairs give 1. Build up to dp[0][4] by checking end matches at each window length. The final cell is dp[0][4] = 4, because s[0]='b' and s[4]='b' match, and dp[1][3]=2, so 2+2=4.
Q: How do you reconstruct one actual longest palindromic subsequence, not just its length?
Backtrack through the filled table starting at dp[0][n-1]. If s[i]==s[j], add s[i] to the front and back of your result and move to dp[i+1][j-1]. If they don't match, move toward the larger neighbor: dp[i+1][j] or dp[i][j-1]. Stop at empty windows or single characters. For "bbbab", this trace recovers "bbbb" — one valid LPS of length 4.
How Verve AI Can Help You Prepare for Your Interview With Longest Palindromic Subsequence
The hardest part of explaining LPS in an interview isn't the recurrence — it's delivering it clearly under live pressure, when the interviewer is watching you and the follow-up could come from any direction. That's a performance skill, and it only improves with repetition against real responses. Verve AI Interview Copilot is built for exactly this: it listens in real-time to your spoken explanation and responds to what you actually said, not a canned script. If your 60-second answer drifts into "DP table stuff" instead of "match ends, drop one side," Verve AI Interview Copilot catches the drift and prompts you back to the core idea. It runs the follow-up questions — "why not greedy?", "what do the indices mean?", "how would you optimize space?" — and it does this while staying completely invisible to any screen share. The result is that by the time you walk into the real interview, you've already survived the follow-ups. Verve AI Interview Copilot turns a problem you understand in theory into one you can explain under pressure.
Conclusion
If you can say the 60-second explanation clearly, derive the recurrence from the end-match decision rather than from memory, and answer one follow-up about why the state is a window boundary pair — you know this problem well enough for the room. The table, the dry run, the reconstruction, the LCS shortcut: all of it flows from the same core idea. Match the ends; if they don't match, drop one side and take the best.
The one thing worth doing before your interview: say the 60-second script out loud, once, without looking at notes. Not to memorize it — to hear whether it sounds like something a person would actually say. If it does, you're ready.
Quinn Okafor
Interview Guidance
