Palindromic substring vs subsequence: why do the two answers differ on the same gene string?
answer
- one of them must be contiguous
- crossing out letters is allowed
- every substring is also a subsequence
- so one answer can never be shorter
- ACGTACGTA: run 1, subsequence 5
basics
~20 sA substring is contiguous; a subsequence keeps order but may skip characters. Every palindromic substring is also a palindromic subsequence, so the subsequence answer is never shorter — and on real sequence data it is usually far longer.
solid answer
~50 sA substring occupies one unbroken stretch of the input, while a subsequence is what survives after crossing out any characters you like, order preserved. Because a contiguous palindrome is also a legal subsequence, the subsequence length is always greater than or equal to the contiguous length, never less. The gap can be enormous: in the marker string `ACGTACGTA` the longest palindromic run of adjacent characters is a single character, yet `ACACA` is a palindromic subsequence of length 5. That is why the recurrences differ — the contiguous version dies on the first mismatched pair, while the subsequence version gets a `max` branch that lets it throw a character away and keep going. Ask which one the requirement wants: highlighting a region for display needs the contiguous answer; scoring symmetry that tolerates insertions needs the subsequence one.
go deeper
Be ready to define both words precisely and give a short string where the two answers differ. Knowing that deleting characters is allowed but reordering is not carries most of the credit here.
Explain why the contiguous recurrence has no max branch while the subsequence one does, and what that single branch does to the size of the answer on noisy input.
Show you interrogate the requirement before coding: which answer does the caller display, score or act on? Point out that minimum-deletions-to-symmetry is the subsequence problem wearing a different name.
Own the cost of getting this wrong across a pipeline: the two answers feed different downstream decisions, and a silent substitution changes reported results without failing any test. Decide where the definition is pinned and documented.
## Two different questions that sound identical "Find the longest palindrome in this sequence" is ambiguous, and the ambiguity changes both the answer and the algorithm. - A **substring** is a contiguous block: pick a start and an end, take everything between them. `CGTA` is a substring of `ACGTACGTA`; `AGA` is not. - A **subsequence** is what remains after deleting any characters you choose, with the survivors kept in their original order. `AGA` is a subsequence of `ACGTACGTA` (delete the rest); so is `ACACA`. A palindrome reads the same forwards and backwards. So "longest palindromic substring" asks for the longest unbroken symmetric stretch, and "longest palindromic subsequence" asks for the longest symmetric pattern you can extract by deletion. ## The inequality is one-directional and always holds Every contiguous palindrome is trivially a subsequence palindrome — deletion of nothing is a legal deletion. Therefore: `length(longest palindromic subsequence) >= length(longest palindromic substring)` never the other way round. Candidates who say "they are basically the same thing, one is just implemented differently" have the relationship backwards in the sense that matters: the two can be arbitrarily far apart. ## A worked marker string Take `ACGTACGTA` (9 characters). Its characters sit at: `A` at 0, 4, 8; `C` at 1, 5; `G` at 2, 6; `T` at 3, 7. - **Contiguous:** no two adjacent characters are equal, and no character equals the one two positions away (A/G, C/T, G/A, T/C, ...). So there is no palindromic run of length 2 or 3, and therefore none longer. The answer is **1**. - **Subsequence:** `A(0) C(1) A(4) C(5) A(8)` spells `ACACA`, a palindrome of length **5**. You cannot do better here: pairing the outer `A`s leaves `CGTACGT` in the middle, whose best is 3. One character versus five, on the same nine-character input. Report the wrong one and the downstream analysis is nonsense. ## Why the recurrences diverge Both are two-dimensional tables indexed by an interval `[i..j]`, and both run in O(n^2) time in their table form, so the difference is not cost — it is one branch. Contiguous (a truth value: "is `s[i..j]` a palindrome?"): ``` dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1] ``` There is no escape hatch. If the ends disagree, the interval is simply not a palindrome; you cannot drop a character, because dropping one would break contiguity. Subsequence (a length: "longest palindromic subsequence inside `s[i..j]`"): ``` if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2 else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]) ``` That `max` **is** the deletion. When the ends disagree you throw one of them away and ask the same question of the smaller interval. This single branch is why the subsequence answer runs away from the contiguous one on noisy data: mismatches cost you a character instead of ending the run. ## Choosing in practice The requirement decides, and it is worth asking out loud in an interview: | The requirement | What it needs | |---|---| | Highlight a symmetric region so a human can see it in the displayed sequence | Contiguous — a subsequence has no region to highlight | | Trim or deduplicate on an exact repeated symmetric block | Contiguous | | Score how close a read is to symmetric, tolerating inserted noise | Subsequence | | Report the fewest deletions that would make the whole read symmetric | Subsequence — the answer is `n` minus the subsequence length | That last row is the one that most often reveals which question was really being asked: minimum deletions to make a sequence a palindrome is the subsequence problem in disguise, and someone who answers it with a contiguous scan will overcount badly. ## The register that scores well State the definition difference in one sentence, give the inequality with its one-line justification, then hand over a concrete pair of numbers on a short string. Finish by asking which the caller actually wants. That covers the concept, the proof and the requirements conversation in under a minute.
- Can the two answers ever be equal?Yes, and often on short or highly symmetric inputs. If the whole string is already a palindrome, both answers are the full length. The gap only opens when symmetry is interrupted by characters that a deletion could remove but a contiguous scan cannot skip.
- Someone asks for the fewest deletions that make a read symmetric — which problem is that?The subsequence one. Whatever you keep must itself be a palindrome and must stay in order, so the best you can keep is the longest palindromic subsequence; the answer is the length of the read minus that value. Solving it with a contiguous scan overestimates the deletions.
- Which of the two has an O(1) extra-space solution?The contiguous one: expanding outward from each center finds the longest symmetric run while holding only a couple of indices. The subsequence version has no such trick — it genuinely needs a table over intervals, because the deletion branch depends on results for two overlapping sub-intervals.
A substring is what you get with two scissor cuts; a subsequence is what is left after crossing out letters anywhere you like.
saying these in an interview costs you the question
- Treats substring and subsequence as interchangeable words
- Claims the contiguous answer can exceed the subsequence answer
- Says a subsequence may reorder characters
- Answers minimum-deletions-to-symmetry with a contiguous scan
- Assumes the same recurrence solves both