Why does the LCS of a gene string with its reverse give its longest palindrome by deletion?
answer
- a palindrome is its own reverse
- so it survives in both copies
- common to the string and its mirror
- the identity is about length only
- the substring version of it is false
basics
~20 sA palindrome reads identically forwards and backwards, so any palindromic subsequence of a string is also a subsequence of its reverse — making it a common subsequence of the two. No common subsequence can beat the best palindrome either, so the two lengths are equal.
solid answer
~50 sTake any palindromic subsequence `p` of the input `s`. Because `p` equals its own reverse, and because reversing `s` reverses the order of every subsequence, `p` also appears as a subsequence of `reverse(s)` — so `p` is a common subsequence of `s` and `reverse(s)`, which gives `LCS(s, reverse(s)) >= LPS(s)`. The opposite bound holds too, so the two lengths are equal, and you can reuse a longest-common-subsequence routine to get the answer in O(n^2). Two cautions. The identity is about **length**: a particular alignment you backtrack out of the common-subsequence table is not guaranteed to read as a palindrome, so reconstruct with the direct interval recurrence over `s` if you need the characters. And the same trick fails for the contiguous problem: the longest common **substring** of a string and its reverse need not be a palindrome at all.
go deeper
Be ready to state that a palindrome reads the same in both directions, so it is present in the string and in the reversed copy — that observation is the whole reduction in one sentence.
Explain the easy direction of the proof, give the cost in time and space, and state the direct interval recurrence with its deletion branch as the alternative that reconstructs the characters.
Show the boundaries of the trick: length versus reconstruction, and the failed substring analogue with a concrete counterexample. Connect it to the deletion and insertion counts a caller usually really wants.
Own the choice between reusing a general alignment routine and writing a purpose-built recurrence: one fewer implementation to maintain against a result that needs a caveat documented wherever it is consumed.
## The claim For any string `s` of length n: `length of the longest palindromic subsequence of s == length of the longest common subsequence of s and reverse(s)` That identity is what lets you solve the palindrome-by-deletion problem with a general-purpose alignment routine instead of writing a bespoke recurrence. ## The easy direction, spelled out Let `p` be any palindromic subsequence of `s`. Two facts combine: 1. `p` is a subsequence of `s` by assumption. 2. Reversing a string reverses the order of every one of its subsequences. So `reverse(p)` is a subsequence of `reverse(s)`. But `p` is a palindrome, so `reverse(p) == p`, and therefore `p` itself is a subsequence of `reverse(s)`. Hence `p` is common to both strings, and the longest common subsequence is at least as long as the longest palindromic one. The other bound — that no common subsequence can exceed the best palindrome — also holds, and it is the half that actually needs an argument rather than a one-line observation. Being able to say *which half is the easy one* is a good signal in an interview; asserting that both are obvious is not. ## Where the identity stops **It is a statement about length.** If you backtrack a common-subsequence table you recover *a* longest common subsequence, and the characters you pull out are not guaranteed to read the same in both directions. If the caller wants the actual symmetric pattern, not just how long it is, use the direct interval recurrence over `s`: ``` dp[i][i] = 1 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]) ``` Read as: if the ends of the interval agree, keep both and recurse inside; otherwise discard one end and take the better of the two options. This is O(n^2) time, and reconstruction walks the same decisions backwards, producing a genuine palindrome by construction. Note the dependency shape — one row below, one column left — which means this table has the same fill-order obligation as any interval DP: shorter spans first. ## The trap: the same trick does not work for contiguous palindromes A very common wrong answer is "so the longest palindromic **substring** is the longest common **substring** of `s` and `reverse(s)`". It is not. A block shared between a string and its reverse only tells you that the block appears somewhere in the string *and* that its reverse appears somewhere in the string — possibly at a different place. Concretely, take the marker `ACAGTCGTGACA`. Its reverse is `ACAGTGCTGACA`. The block `ACAGT` (length 5) appears in both, because the string also contains `TGACA` further along. But `ACAGT` is not a palindrome, and the longest contiguous palindrome in that marker is only length 3 (`ACA`, or `GTG`). So the shared-block method reports 5 and hands back a non-palindrome. The fix people reach for — check that the two occurrences are mirror positions of one another — turns the neat reduction into fiddly index bookkeeping, which is why the contiguous problem is normally solved by centre expansion or an interval table instead. ## Two derived quantities interviewers like - **Minimum deletions to make `s` symmetric** = `n` minus the longest palindromic subsequence length. Everything you keep must itself be symmetric and in order, so keeping the maximum is exactly the same optimisation. - **Minimum insertions to make `s` symmetric** = the same number. Every character you would have deleted can instead be mirrored by an insertion on the other side, which is a pleasing thing to be able to explain rather than memorise. ## Cost, and where the space goes Both the reduction and the direct recurrence are O(n^2) time and O(n^2) space in their plain table form. If you only need the length, the space collapses to O(n) because each cell depends on the previous row alone; if you need the characters, keep the full table or re-derive the path with a divide-and-conquer reconstruction. There is no O(1)-space trick here, unlike the contiguous problem — the deletion branch means the answer for an interval is not determined by a local expansion around a centre. ## Answering it well Give the one-line argument for the easy direction, state the identity as a statement about length, then volunteer the two caveats: reconstruction, and the fact that the analogous substring claim is false with a concrete counterexample ready. That sequence turns a memorised trick into demonstrated understanding.
- Does the same reduction find the longest palindromic substring using the longest common substring?No. A shared block only means the block appears in the string and its reverse appears somewhere in the string, possibly elsewhere. In the marker ACAGTCGTGACA the shared block ACAGT has length 5 and is not a palindrome, while the longest contiguous palindrome is length 3.
- How do you get the fewest deletions that make a read symmetric?Subtract the longest palindromic subsequence length from the read length. Whatever survives the deletions must be symmetric and in original order, so the best possible survivor is that subsequence and everything else must go. The minimum number of insertions that achieves symmetry is the same value.
- If you need the actual palindrome and not just its length, which method do you use?The direct interval recurrence over the string itself, backtracking the decisions that built each cell. It yields a genuine palindrome by construction. The identity with the reverse guarantees the length only, so a path recovered from that alignment is not automatically symmetric.
- Can this be done in O(1) extra space like the contiguous version?No. Centre expansion works for contiguous palindromes because a palindrome grows locally around one centre. The deletion branch destroys that locality: the answer for an interval depends on two overlapping sub-intervals, so you need a table, or O(n) rows if only the length is wanted.
saying these in an interview costs you the question
- Claims the same trick works for contiguous palindromes
- Says any recovered alignment is automatically a palindrome
- States minimum deletions equals the subsequence length itself
- Thinks reversing the string can change subsequence order arbitrarily
- Expects a constant-space solution for the deletion version