Palindrome Patterns

Palindromes are a favourite interview topic because the same word covers three genuinely different difficulty tiers:

1. Verify one string is a palindrome — two pointers, $O(n)$, Easy.
2. Find palindromic substrings inside a string — expand around centre, $O(n^2)$, Medium.
3. Build a palindrome by deleting or inserting — interval DP, $O(n^2)$, Medium to Hard.

The mistake that costs the most time is reaching for tier 3 machinery on a tier 2 problem. This page separates them, and gives you the cue for each.

What you’ll learn

• The two-pointer verification template, and the “at most one deletion” variant.
• Expand around centre: why there are 2n - 1 centres, not n.
• Why “substring” means expand-around-centre and “subsequence” means DP — the single most useful distinction on this page.
• Three real LeetCode problems solved in the browser: 5, 647, 680.

The cue

Which palindrome tier are you in?

The problem says	Tier	Technique
“is s a palindrome”	Verify	Two pointers, $O(n)$
“substring” (contiguous)	Find	Expand around centre, $O(n^2)$
“subsequence” (may skip)	Build	Interval DP, $O(n^2)$
“minimum insertions/deletions to make it a palindrome”	Build	DP — usually n - LPS(s)
“partition into palindromes”	Search	Backtracking + a palindrome table
“at most one deletion allowed”	Verify	Two pointers with a single branch

Substring vs. subsequence is the whole game. "bbbab" has longest palindromic substring "bbb" (length 3) and longest palindromic subsequence "bbbb" (length 4). Misreading one for the other means solving a different problem correctly.

Tier 1 — verify with two pointers

is_palindrome.py

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
 
 
print(is_palindrome("racecar"))   # True
print(is_palindrome("abca"))      # False

$O(n)$ time, $O(1)$ space. s == s[::-1] is also $O(n)$ but allocates a reversed copy, so it is $O(n)$ space — fine to mention, and fine to use unless asked for constant space.

For LC 125 the only additions are skipping non-alphanumeric characters and lower-casing:

valid_palindrome_125.py

def is_palindrome_alnum(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():    # skip junk
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True
 
 
print(is_palindrome_alnum("A man, a plan, a canal: Panama"))   # True

The inner skip loops still need left < right

On an input like ".," — all punctuation — an unguarded while not s[left].isalnum(): left += 1 runs straight off the end of the string. Both inner loops need the left < right guard, not just the outer one.

Tier 2 — expand around centre

Every palindrome has a centre. Grow outward from each possible centre while the characters match; each expansion step is $O(1)$ and finds a new palindrome.

The detail that catches people: a palindrome of even length has its centre between two characters. So there are 2n - 1 centres — n single-character centres and n - 1 gaps.

expand_around_centre.py

def longest_palindrome(s):
    if not s:
        return ""
    best_left, best_len = 0, 1
 
    def expand(left, right):
        nonlocal best_left, best_len
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > best_len:
                best_left, best_len = left, right - left + 1
            left -= 1
            right += 1
 
    for i in range(len(s)):
        expand(i, i)          # odd-length centre: a single character
        expand(i, i + 1)      # even-length centre: the gap after i
 
    return s[best_left:best_left + best_len]
 
 
print(longest_palindrome("babad"))   # "bab"  ("aba" is equally correct)
print(longest_palindrome("cbbd"))    # "bb"

Forgetting the even centres is the classic bug

A solution that only calls expand(i, i) returns "b" for "cbbd" instead of "bb". It passes plenty of test cases — any input whose answer happens to be odd-length — which makes it a nasty bug to notice. Always call both.

Approach	Time	Space
Check every substring	$O(n^3)$	$O(1)$
DP table is_pal[i][j]	$O(n^2)$	$O(n^2)$
Expand around centre	$O(n^2)$	$O(1)$
Manacher’s algorithm	$O(n)$	$O(n)$

Expand-around-centre is the interview answer: same time as the DP with $O(1)$ space, and far less code. Manacher’s is the theoretically optimal $O(n)$ solution — know that it exists and is the answer to “can you do better than $O(n^2)$”, but nobody sane expects you to derive it live.

Tier 3 — when it becomes DP

Once you may skip characters (subsequence) or modify the string (insert/delete), centres stop helping and you need interval DP over (i, j) ranges.

The one identity worth memorising:

$\text{min insertions to make } s \text{ a palindrome} = n - \text{LPS}(s)$

where $\text{LPS}$ is the longest palindromic subsequence — and $\text{LPS}(s) = \text{LCS}(s, \text{reverse}(s))$. So LC 1312 reduces to a longest-common-subsequence you already know how to write. These live in Classic DP and DP on Grids and Intervals.

Visual intuition

A palindrome is defined by its centre, and there are only $2n - 1$ centres. That reframing is what turns an $O(n^3)$ brute force into $O(n^2)$:

arrayExpand from every centre — odd and evenLC 5 · O(n^2) time, O(1) space

b0a1b2a3d4

1def longest_palindrome(s):2    best = (0, 0)3    for c in range(len(s)):4        for lo, hi in ((c, c), (c, c + 1)):     # odd, then even5            while lo >= 0 and hi < len(s) and s[lo] == s[hi]:6                lo -= 1; hi += 17            lo, hi = lo + 1, hi - 1             # step back inside8            if hi - lo > best[1] - best[0]:9                best = (lo, hi)10    return s[best[0]:best[1] + 1]

centres9

setupA palindrome is defined by its **centre**, and there are only $2n - 1$ centres: $n$ single characters (odd lengths) and $n - 1$ gaps between characters (even lengths). Checking every substring is $O(n^3)$; expanding from every centre is $O(n^2)$ with no extra memory.

Play‹›1/19⟲

Both centre kinds must be tried at every index: n single characters for odd lengths, n-1 gaps for even ones. Checking only odd centres misses 'abba' entirely, and that omission passes a surprising number of test cases.

Complexity

Approach	Time	Space
Check every substring	$O(n^3)$	$O(1)$
DP over [i][j] is-palindrome	$O(n^2)$	$O(n^2)$
Expand around centre	$O(n^2)$	$O(1)$
Manacher’s algorithm	$O(n)$	$O(n)$

Expand-around-centre is the answer to give: same time as the DP with none of the space. Manacher’s is worth naming — it shows you know $O(n)$ exists — but almost never worth writing, and saying “I know it exists and would look it up” reads better than a half-remembered attempt.

Practice — real LeetCode problems

LC 5 — Longest Palindromic Substring · Medium

Problem. Given a string s, return the longest palindromic substring in s.

Constraints. 1 <= len(s) <= 1000, digits and English letters.

Examples. "babad" gives "bab" — "aba" is also accepted · "cbbd" gives "bb"

Why this test checks lengths, not the exact string

When several longest palindromes tie, LeetCode accepts any of them. So the test below checks the length of your answer plus a validity assertion (that what you return really is a palindrome and really is a substring of the input) rather than demanding one specific string. Returning "aba" for "babad" passes, as it should.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Every palindromic substring is determined by its centre and its radius. Try all 2n - 1 centres and expand each while the characters match; the longest one found is the answer.

Time $O(n^2)$ — 2n - 1 centres, each expanding at most $O(n)$. Space $O(1)$ beyond the output.

Track (best_left, best_len) instead of building strings inside the loop. Slicing on every improvement turns the inner work into $O(n)$ and the whole thing into $O(n^3)$ in the worst case (a long run of identical characters).

Follow-ups you should expect:

• “Can you do better than $O(n^2)$?” Yes — Manacher’s algorithm is $O(n)$. It transforms the string (interleaving separators so every palindrome is odd-length) and reuses previously computed radii via a mirror argument. Naming it and sketching why it works is the expected depth; deriving it live is not.
• “Count them instead of finding the longest?” LC 647 — same expansion, increment a counter on every successful step.
• “Longest palindromic subsequence?” Different problem entirely — interval DP, LC 516. "bbbab" gives 4, not 3.
• “Why is the DP table worse?” Same $O(n^2)$ time but $O(n^2)$ space, and more code. It is only preferable when you need the full is_pal[i][j] table for something else — which is exactly what LC 131 Palindrome Partitioning wants.

LC 647 — Palindromic Substrings · Medium

Problem. Given a string s, return the number of palindromic substrings in it. Substrings at different positions count separately even if they are identical.

Constraints. 1 <= len(s) <= 1000, lowercase English letters.

Examples. "abc" gives 3 ("a", "b", "c") · "aaa" gives 6 ("a"×3, "aa"×2, "aaa")

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

This is LC 5 with the accumulator swapped. Each time an expansion succeeds, the current [left, right] window is itself a palindromic substring, so increment.

Time $O(n^2)$. Space $O(1)$.

Worth checking "abba" by hand to see all six: "a", "b", "b", "a", "bb", "abba". The four single characters always count — every string of length n has at least n palindromic substrings, which is a useful sanity floor. "abc" giving exactly 3 confirms you are counting singles.

Follow-ups you should expect: “Count distinct palindromic substrings?” — genuinely harder; you need to deduplicate, which means a set of strings ($O(n^2)$ space) or the Eertree / palindromic-tree structure for the efficient answer. “Longest instead of count?” — LC 5. “Count palindromic subsequences?” — interval DP, and the counting version (LC 730) is Hard.

LC 680 — Valid Palindrome II · Easy

Problem. Given a string s, return True if it can be made a palindrome by deleting at most one character.

Constraints. 1 <= len(s) <= 10^5, lowercase English letters.

Examples. "aba" gives True (already one) · "abca" gives True (delete "c" or "b") · "abc" gives False

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Walk inward. While characters match there is no decision to make. At the first mismatch, the deleted character must be one of s[left] or s[right] — no other deletion can fix this particular pair. So branch once: check s[left+1 .. right] and s[left .. right-1] as plain palindromes.

Time $O(n)$ — the main loop is $O(n)$ and the branch happens at most once, costing another $O(n)$. Space $O(1)$.

Try both sides, and don’t use a counter

Two tempting shortcuts are wrong:

• Only skipping one side. "cbbcc" needs the right character dropped, "deeee" needs the left. Checking only one direction fails half the cases.
• A deletions_used counter in the main loop. It feels natural but is incorrect: after a mismatch, “which pointer do I advance?” is a real branch, and a counter gives you no way to explore both. The two explicit is_pal calls are the branch.

"eccer" is a good manual check: mismatch at e vs r, and dropping the right character leaves "ecce" — a palindrome.

Follow-ups you should expect: “At most k deletions?” — the branching approach becomes exponential, so switch to DP: the answer is len(s) - LPS(s) <= k, i.e. LC 1312’s identity. “Return which character to delete?” — return the index from whichever branch succeeded. “Deletions from both strings to make them equal?” — LC 583, an edit-distance variant.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 234 is the palindrome problem people over-think

Palindrome Linked List has an obvious $O(n)$-space answer: copy the values into a list and two-pointer it. That is perfectly acceptable and you should say it.

The $O(1)$-space answer composes two patterns you already have: fast and slow pointers to find the middle, then in-place reversal of the second half, then a straight comparison. A good interviewer will ask whether you restore the list afterwards — mutating the caller’s input is a real design flaw, and noticing it unprompted reads very well.

10 problems

4 easy4 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○9Palindrome NumbereasyNo string conversion allowed: reverse only half the digitsLeetCode Top Interview 150
• ○125Valid PalindromeeasyTwo pointers, skipping non-alphanumerics; guard the inner skip loopsNeetCode 150Blind 75LeetCode Top Interview 150
• ○234Palindrome Linked ListeasyFind the middle, reverse the second half, compare -- $O(1)$ space
• ○680Valid Palindrome IIeasyOne deletion means one branch -- try both sides
• ○5Longest Palindromic SubstringmediumExpand around all `2n - 1` centresNeetCode 150Blind 75LeetCode Top Interview 150
• ○131Palindrome PartitioningmediumBacktracking, ideally with a precomputed `is_pal[i][j]` tableNeetCode 150
• ○516Longest Palindromic Subsequencemedium**Subsequence**, so interval DP -- or `LCS(s, reversed(s))`
• ○647Palindromic SubstringsmediumSame expansion, counting instead of maximisingNeetCode 150Blind 75
• ○132Palindrome Partitioning IIhard
• ○1312Minimum Insertion Steps to Make a String Palindromehard`n - LPS(s)` -- the identity does all the work

Dry run

s = "babad". Every centre, both kinds.

centre	kind	expansion	result	best so far
0	odd	b then lo < 0	"b" (1)	"b"
0–1	even	b ≠ a	none	"b"
1	odd	a, then b==b → bab, then out of range	"bab" (3)	"bab"
1–2	even	a ≠ b	none	"bab"
2	odd	b, then a==a → aba	"aba" (3)	"bab" (tie, first kept)
2–3	even	b ≠ a	none	—
3	odd	a, then b ≠ d	"a" (1)	—
3–4	even	a ≠ d	none	—
4	odd	d	"d" (1)	—

Answer "bab" — and "aba" is equally valid, which the problem statement explicitly allows. Worth confirming with the interviewer rather than assuming.

The ±1 after the loop is where this goes wrong

The while exits after lo and hi have already moved past the failing comparison, so the actual palindrome is s[lo+1 : hi]. Forgetting to step back inside gives a length two too large, and the bug is invisible on single-character answers.

The variant map

Variant	Change to the template	Canonical problem
Longest palindromic substring	track the widest expansion	5 Longest Palindromic Substring
Count all palindromic substrings	add 1 per successful expansion step instead of taking a max	647 Palindromic Substrings
Is it a palindrome, ignoring non-alphanumerics	two pointers with skip conditions, no centres needed	125 Valid Palindrome
Palindrome after deleting one character	two pointers; on the first mismatch try skipping either side	680 Valid Palindrome II
Longest palindromic subsequence	not contiguous — this is LCS of s and reversed(s)	516 Longest Palindromic Subsequence
Partition into palindromes	backtracking with an is-palindrome check, memoised	131 · 132 Palindrome Partitioning

Substring and subsequence are different problems with different tools

Expand-around-centre requires contiguity. The moment a problem says subsequence, centres are meaningless and it becomes a DP — specifically LCS of the string against its own reverse. Reading past that word is a common and expensive mistake.

Interview follow-ups

They ask	What they’re checking	The answer
“Substring or subsequence?”	Careful reading	Substring is contiguous (centres); subsequence may skip (DP). "bbbab" gives 3 vs 4
“Why 2n - 1 centres?”	Whether you found the even case	n character centres plus n - 1 gaps, because even-length palindromes centre between characters
“Beat $O(n^2)$?”	Breadth	Manacher’s algorithm, $O(n)$ — name it and sketch the mirror/radius-reuse idea
“Why not the DP table?”	Judgement	Same $O(n^2)$ time but $O(n^2)$ space; only worth it when you need the whole table (LC 131)
“At most k deletions?”	Knowing when branching dies	Branching goes exponential; use len(s) - LPS(s) <= k
”$O(1)$ space on a linked list?”	Composition	Fast/slow to the middle, reverse the second half, compare — then consider restoring it
“Count distinct palindromic substrings?”	Depth	Deduplicate with a set ($O(n^2)$ space), or use a palindromic tree (Eertree)

Edge-case checklist

• Single character — always a palindrome; the answer to LC 5 has length 1, and LC 647 counts 1.
• Two characters — "ac" gives "a" (or "c"); "bb" gives "bb". The fastest check that you handled even centres.
• All identical — "aaaa"; the worst case for expansion, and where slicing inside the loop turns $O(n^2)$ into $O(n^3)$.
• No palindrome longer than 1 — "abc"; make sure best_len starts at 1, not 0.
• Ties for longest — multiple valid answers; do not assume one exact string.
• All non-alphanumeric (LC 125) — ".," must return True and must not run off the end of the string.
• Mismatch needing the right-side deletion (LC 680) — "cbbcc"; catches one-sided solutions.
• Empty string — vacuously a palindrome, though most of these problems guarantee at least one character.

Self-check

pch.quizTag Palindrome patterns — self-check

1. How many centres does a string of length n have, and why does it matter?

   A n — one per character B 2n - 1 — n single characters for odd lengths plus n-1 gaps for even ones C n squared — one per substring D n/2 — only the first half needs checking
   pch.quizShowAnswer

   B — 2n - 1 — n single characters for odd lengths plus n-1 gaps for even ones — Missing the even centres is the classic bug: it silently fails on any even-length palindrome such as abba, while still passing plenty of tests.

2. After the expansion while-loop exits, why adjust lo and hi by one?

   A To include the centre B Because the loop exits only after both pointers have moved past the failing comparison, so the real palindrome is s[lo+1:hi] C To handle the empty string D No adjustment is needed
   pch.quizShowAnswer

   B — Because the loop exits only after both pointers have moved past the failing comparison, so the real palindrome is s[lo+1:hi] — The loop condition is checked after the increment, so on exit both pointers sit one step outside. Forgetting the step back reports a length two too large, and single-character answers hide it.

3. A problem asks for the longest palindromic SUBSEQUENCE. Does expand-around-centre apply?

   A Yes — subsequence and substring are the same here B No — centres require contiguity. This is LCS of the string against its reverse C Yes, with a small modification to the while condition D Only for even-length answers
   pch.quizShowAnswer

   B — No — centres require contiguity. This is LCS of the string against its reverse — One word changes the entire problem and the entire toolset. A palindromic subsequence need not be contiguous, so there is no centre to expand from — it becomes O(n squared) DP.

4. Counting all palindromic substrings (LC 647) — what changes?

   A Nothing — count the centres B Add 1 for each successful expansion step rather than tracking a maximum, since every step is itself a distinct palindrome C Square the answer D Use a hash set of substrings
   pch.quizShowAnswer

   B — Add 1 for each successful expansion step rather than tracking a maximum, since every step is itself a distinct palindrome — Each successful expansion from a centre reveals one more palindrome. Same loop, a counter instead of a max — which is why recognising the shared template is worth more than memorising either problem.

5. Should you write Manacher’s algorithm when asked to beat O(n squared)?

   A Yes, always B Name it, explain that it achieves O(n) by reusing mirror information, and say you would look up the details — a half-remembered attempt is worse than a clear acknowledgement C No, and do not mention it D Only if you have memorised it
   pch.quizShowAnswer

   B — Name it, explain that it achieves O(n) by reusing mirror information, and say you would look up the details — a half-remembered attempt is worse than a clear acknowledgement — Interviewers are testing awareness of the landscape, not recall of a rarely-used algorithm. Naming it and being honest about the details scores better than a broken implementation.

Recall card

• Cue — “palindromic substring” (contiguous). If it says subsequence, stop — that is LCS against the reverse.
• Key idea — a palindrome is defined by its centre, and there are $2n - 1$ centres: n characters and n - 1 gaps.
• Template — for each centre, expand while s[lo] == s[hi], then step back inside by one and measure.
• Complexity — $O(n^2)$ time, $O(1)$ space. Manacher’s is $O(n)$ — name it, do not write it.
• Remember — try both centre kinds at every index; adjust by ±1 after the loop; for counting, add 1 per expansion step instead of taking a max.

Recap

• Three tiers, three techniques. Verify with two pointers ($O(n)$), find substrings by expanding around centres ($O(n^2)$, $O(1)$ space), build/modify with interval DP.
• Substring vs. subsequence is the distinction that decides which tier you are in. Read the problem statement twice.
• There are 2n - 1 centres — always expand both (i, i) and (i, i + 1).
• Track indices, not strings, inside expansion loops; slicing per improvement can add a factor of n.
• “At most one deletion” is one branch, not a counter — and you must try both sides.
• min insertions = n - LPS(s), and LPS(s) = LCS(s, reverse(s)) — one identity that collapses several Hard problems into a known DP.
• Manacher’s gives $O(n)$; know it exists, and that expand-around-centre is what you are expected to write.

Next: Trie Patterns — the prefix tree, and the problems that are unreasonably easy once you have one.