DP IX — Palindromes

Review boundary and corrected contracts

Center expansion shares the palindrome-extension property but does not memoize a DP table. It uses constant working space plus the returned substring. Increasing length is one valid table order; descending left endpoints with increasing right endpoints also respect dependencies.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Write expand-around-centre from memory and know when it is the right tool versus when repeated substring queries justify a 2D palindrome table.

Series: LeetCode — From Basics to Production-Ready · Session 41 / 65 · Phase 2 · Dynamic programming

Prerequisites. Two-pointer movement (L07) and, for the partitioning problems only, basic backtracking (L30–L31). The DP table variant assumes L33–L35 but the expansion method needs none of it.

Watch first

Optional resources retained from the original lesson; video availability and contents were not rechecked in this review. The worked explanations below are self-contained.

• Longest Palindromic Substring — Leetcode 5 — NeetCode.
• Palindromic Substrings — Leetcode 647 — NeetCode.
• Longest Common Subsequence — Leetcode 1143 — NeetCode.

Why this session exists

Expand-around-centre is O(n²) and so is the DP table, so on paper this session has nothing to teach — pick either. Expansion has fewer state and fill-order decisions; the table pays for storage by making later substring queries constant-time. That tradeoff is the point, not a promised coding time.

The DP table for palindromes has a fill-order trap that most people hit at least once. dp[i][j] depends on dp[i+1][j-1], which is below and left of the cell being filled. A naive row-major loop reads a cell that has not been written yet, and the resulting bug does not crash — it silently reports shorter palindromes. To fix it you iterate by substring length, or you iterate i downward. Neither is hard, but both are the kind of thing you forget at the whiteboard.

Expand-around-centre has no fill order at all. You pick a centre, you walk outward while the characters match, you stop. There are 2n - 1 centres because a palindrome can be centred on a character or between two characters, and that is the only subtlety in the entire method.

So the recommendation is straightforward: for "find the longest palindromic substring" and "count all palindromic substrings", expand around centres. For "partition the string into palindromic pieces" you need to answer is s[i:j+1] a palindrome repeatedly during a backtracking search, and there a precomputed boolean table earns its keep. Knowing which situation you are in is what this session buys you.

Blank-file warm-up

Five minutes, empty file, no notes. Write expand(l, r) — the helper that walks two pointers outward while s[l] == s[r]:

1. The bounds check and the character comparison, in the correct order.
2. What the pointers hold when the loop exits, and how to recover the substring from them.
3. The driver loop that calls it for both odd and even centres.

The part that trips people is step 2. When the loop terminates, l and r have already moved one step too far, so the palindrome is s[l+1:r]. Getting that wrong by one is the classic failure and it is worth burning into muscle memory now.

Pattern anatomy

The shape that summons this pattern: a question about palindromic substrings of a single string, with n in the low thousands. Not two strings — that was L40. One string, and a symmetric-structure question.

The invariant behind expansion is trivially simple, which is precisely why it is reliable: at every step of the walk, s[l+1:r] is a palindrome. You extend it by one character on each side if and only if s[l] == s[r]. The moment they differ, or a pointer runs off the end, the palindrome centred here is maximal.

def expand(s: str, l: int, r: int) -> tuple[int, int]:
    """Walk outward while s[l] == s[r]. Returns (start, end_exclusive)."""
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return l + 1, r          # loop overshot by one on each side
 
def longest_palindrome(s: str) -> str:
    best_l, best_r = 0, 0
    for c in range(len(s)):
        for l, r in ((c, c), (c, c + 1)):     # odd centre, then even centre
            a, b = expand(s, l, r)
            if b - a > best_r - best_l:
                best_l, best_r = a, b
    return s[best_l:best_r]

There are 2n−1 nonempty centers for n>0. This code also tries one harmless out-of-range even center. Each expansion costs O(n) in the worst case; total O(n²) time and O(1) working space, plus the O(length of answer) returned Python substring.

The DP table records the same inside-to-outside dependency, but organises it by endpoints rather than centres. Put the left endpoint on the row axis and the right endpoint on the column axis: single-character palindromes sit on the diagonal, and longer intervals occupy successive bands above it. A cell can be true only when its endpoints match and its shorter interior is already known to be a palindrome. This keeps the same quadratic time as expansion, but stores a quadratic table of answers for later substring queries:

def palindrome_table(s: str) -> list[list[bool]]:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = True                        # length 1
    for i in range(n - 1):
        dp[i][i + 1] = (s[i] == s[i + 1])      # length 2
    for length in range(3, n + 1):             # one dependency-respecting order
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
    return dp

Note the outer loop over length. That is the fill order that makes dp[i+1][j-1] available before it is read. Descending left endpoints with ascending right endpoints also works; increasing-left row-major order can read an unfilled interior.

The cue

You are looking at a palindrome problem when the statement contains these tells:

1. The word "palindrome" or "reads the same forwards and backwards". Obvious, but the follow-up matters: is it about substrings (contiguous) or subsequences (skippable)? Longest Palindromic Subsequence is a completely different problem — it is the LCS of s and reversed s, a two-string grid from L40.
2. n up to roughly 1000. Quadratic intended. If n is 10^5 and the problem still wants the longest palindromic substring, the intended answer is Manacher's algorithm, which is genuinely O(n) and genuinely not worth memorising for most design reviews.
3. "Count all" rather than "find the longest". Counting is the same expansion loop with a counter instead of a max — each successful expansion step is one more palindromic substring. That is a two-line change, not a new algorithm.
4. "Partition" or "cut" or "split into pieces such that each piece is a palindrome". This is expansion plus backtracking, and it is where the precomputed table pays off, because the backtracking asks the same is-palindrome question thousands of times.
5. "Minimum cuts" rather than "all partitions". That is a second DP layer on top of the table: cuts[i] = minimum cuts for the prefix ending at i. Two DPs stacked, which is worth recognising as its own shape.

The single sharpest distinction is tell 1's follow-up. Substring versus subsequence changes the entire approach, and problem setters know that people skim.

Guided solve

Longest Palindromic Substring — given s, return the longest substring that is a palindrome.

The brute force is worth naming before discarding: enumerate all O(n²) substrings and check each in O(n), giving O(n³). Say this out loud, then say why you are rejecting it — you are re-verifying overlapping work, because checking s[2:8] re-examines everything you already examined when checking s[3:7].

That observation points directly at the fix. A palindrome of length k contains a palindrome of length k-2 at its core. So instead of starting from substrings and checking them, start from cores and grow them. Every palindrome has exactly one centre, so if you try every possible centre you will find every possible palindrome, and each successful outward step discovers one additional palindrome in constant work. The total steps, not a fresh scan of every discovered substring, give the quadratic bound.

The centres are the subtle part. For odd-length palindromes like "aba" the centre is a character, index 1. For even-length ones like "abba" the centre sits between indices 1 and 2 — there is no character there. So you run two expansions per index: expand(i, i) and expand(i, i+1). The second one for the final index has r = n, which the bounds check rejects immediately, so it costs O(1) and needs no special case.

Now the off-by-one. Inside expand, the loop condition is checked before the decrement and increment, so when it fails the pointers have already stepped past the last matching pair. The palindrome is therefore s[l+1 : r], half-open. Return (l+1, r) and compare lengths as r - (l+1), which is what the code above does by returning the pair directly.

Trace "babad" at centre index 2 ('b'): l=r=2, characters match trivially, step out to l=1, r=3 — s[1]='a', s[3]='a', match, step out to l=0, r=4 — s[0]='b', s[4]='d', mismatch, loop exits. Return (1, 4), giving s[1:4] = "aba". Length 3. Correct.

If a reviewer asks for O(n), the answer is Manacher's algorithm — it reuses previously computed palindrome radii to skip redundant expansion, exploiting the mirror symmetry around the current rightmost palindrome. Naming it and sketching the idea in two sentences is almost always sufficient. Writing it from memory is rarely expected and rarely a good use of preparation time compared to, say, owning graph traversal cold.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Palindromic Substrings — count every palindromic substring, including single characters and duplicates at different positions. Same expansion driver; think about what to increment and where inside the loop.
• Palindrome Partitioning — return all ways to cut s so every piece is a palindrome. Backtracking over cut positions. Precompute the boolean table first and the recursion becomes very short.

If both land early, attempt Palindrome Partitioning II (minimum cuts) — it stacks a one-dimensional, O(n²)-time prefix DP on top of the same table and is a good test of whether you can layer two DPs without confusing their indices.

Worked answers — count and partition

Counting counts positions, not distinct string values: "aaa" has three length-1, two length-2 and one length-3 palindromic substrings, totalling 6. Increment once for each successful expansion, including the initial singleton match.

def count_palindromic_substrings(s):
    count = 0
    for c in range(len(s)):
        for l, r in ((c, c), (c, c + 1)):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                count += 1
                l -= 1
                r += 1
    return count
 
assert count_palindromic_substrings("aaa") == 6
assert count_palindromic_substrings("") == 0

For all partitions, precompute palindrome_table(s), then backtrack from a prefix boundary start. Try each end >= start with table[start][end] true, append s[start:end+1], recurse from end+1, and pop that piece on return. At start == len(s), emit a copy of the current pieces. On "aab" the answers are ["a", "a", "b"] and ["aa", "b"]. The table makes each eligibility check O(1), but cannot make enumeration polynomial: a nonempty all-equal string has 2^(n-1) cut patterns, and copying each output costs O(n) characters.

Common failure modes

Off-by-one on the returned bounds. Returning (l, r) instead of (l+1, r) from the expansion. The reported interval is one position too wide on the left; r is already exclusive. Python negative slicing can mask the mistake: the mutated helper returns (-1, 1) on "a", and s[-1:1] still gives "a". On "ab" at centre (0, 0), the same bounds slice to the empty string, not the centre's "a"; use bounds assertions, not just a longest-length check.

Forgetting the even-length centres. Running only expand(i, i) gives correct answers on every odd-length palindrome and silently misses "abba" entirely. Test with "cbbd" — the answer must be "bb", and an odd-only version returns a single character.

Row-major fill order in the DP table. dp[i][j] needs dp[i+1][j-1], which lives in a later row. A naive for i: for j: loop reads False from an unfilled cell and reports shorter palindromes than exist. Iterate by substring length, or iterate i from n-1 down to 0.

Comparing lengths with the wrong expression. Keeping best as a string and doing if len(candidate) > len(best) is fine, but slicing on every centre can copy O(n) characters per candidate, adding allocation work and O(n) peak temporary space while preserving the O(n²) worst-case time bound. Track indices, slice once at the end.

Solving subsequence when the problem said substring. Longest Palindromic Subsequence allows skipping characters and is a different algorithm. Reading carefully is a skill; this is where it is tested.

Myth: The DP table is the 'real' dynamic programming solution, so expand-around-centre must be a hack that is somehow inferior.

Why: They are the same asymptotic complexity, and expansion uses strictly less memory — O(1) versus O(n^2). Expansion is also a form of the same insight: it exploits the fact that a palindrome's core is a palindrome, which is exactly the optimal substructure the table encodes. The difference is only that expansion computes cells lazily along the diagonal chains it actually needs, while the table computes all n^2 cells whether or not they are reachable. Expansion shares the palindrome-extension rule but does not memoize a DP table; the recurrence insight does not make the two algorithms identical.

Steps 1: Because a palindrome reads the same in both directions, removing one character from each end of a palindrome leaves a palindrome.

Steps 2: Because that shrinking process terminates at either a single character or an empty gap between two equal characters, every palindrome has exactly one centre.

Steps 3: Because the centre is either a character or a gap, there are exactly 2n - 1 possible centres in a string of length n.

Steps 4: Because the property is symmetric, growing outward from a centre extends the palindrome by one character on each side precisely when those two characters are equal.

Steps 5: Because each expansion halts at the first mismatch, the work per centre is proportional to the length of the palindrome found there, bounded by n.

Steps 6: Therefore total work is O(n^2) worst case, and the testable prediction is that a string of n identical characters is the slowest input — every centre expands maximally — while a string of n distinct characters finishes in near-linear time.

Picture: A zipper. You put your fingers at the centre and pull outward with both hands simultaneously. The zipper opens as long as the teeth on both sides match; the instant one pair does not, you stop. Every possible zipper start is a centre, and you try them all.

Trigger: Fires when a single string is asked about symmetric substrings — longest, count, or partition into palindromic pieces.

Name: Expand around centre

Gain: O(1) extra space, no fill-order trap, roughly ten lines, and it can be written correctly under pressure without a scratch grid

Cost: One expansion discovers all nested palindromes at its centre, but this implementation retains only its maximal interval. Arbitrary later endpoint queries need another check unless you store additional information.

Name: 2D boolean DP table

Gain: Answers is s\[i..j] a palindrome in O(1) any number of times, which makes partitioning problems short and fast

Cost: O(n^2) memory, and the length-ordered fill is a genuine trap that produces a silent wrong answer if you get it backwards

Pick: Expand around centre when the question is answered by a single scan — longest palindromic substring or counting all palindromic substrings. Build the table when a search will query is-palindrome many times for the same index pairs, which is exactly Palindrome Partitioning and Palindrome Partitioning II.

Memory hook — "2n minus 1 centres, l plus 1 to r"

Two numbers carry this entire session, and both are the ones people get wrong.

2n - 1 centres. A palindrome is either centred on a character (n of those) or in the gap between two characters (n - 1 of those). Sum: 2n - 1. If your driver loop does not call expand twice per index, you are silently missing every even-length palindrome, and the bug is invisible on inputs like "babad" where the answer happens to be odd-length. The peg: "characters and gaps" — count both, always.

s[l+1 : r]. The loop condition is checked before the pointers move, so on exit they have already stepped one past the last matching pair. The palindrome is the half-open slice l+1 to r. The peg: "the loop overshoots, so step back in on the left." Note that you do not step back on the right, because the slice bound is exclusive — the asymmetry is what makes it memorable and what makes it easy to over-correct.

The shape-of-the-code peg is four beats: guard both bounds, compare, step out, return the pair. Returning the bounds is convenient. Returning only a length can also work if the caller retains the centre and its odd/even convention, from which it can recover the bounds.

And for the family: substring means contiguous means expand; subsequence means gappy means grid. Read the noun before you pick the method.

What reviewers actually ask

Palindrome questions are common as warm-ups and as the first half of two-part problems, because they are quick to state and the naive cubic solution is tempting.

• 5 · Longest Palindromic Substring (Medium) — Practice selection. Probing whether you get past the O(n^3) enumeration to centre expansion. Follow-up: "can you do O(n)?" — name Manacher's algorithm and sketch the mirror-reuse idea.
• 647 · Palindromic Substrings (Medium) — Practice selection. Probing whether you see it is the same driver with a counter. Follow-up: return the distinct palindromes rather than the count.
• 131 · Palindrome Partitioning (Medium) — Practice selection. Probing backtracking composed with a palindrome check. Follow-up: precompute the boolean table so each check is O(1) instead of O(n).
• 132 · Palindrome Partitioning II (Hard) — Practice selection. Probing whether you can layer a one-dimensional, O(n²)-time prefix DP on top of the table without tangling the indices.
• 516 · Longest Palindromic Subsequence (Medium) — Practice selection. Probing the substring-versus-subsequence distinction directly. It is LCS of s with s reversed — a different session's tool, deliberately.
• 125 · Valid Palindrome (Easy) — Practice selection. The two-pointer warm-up, usually asked before a harder question. Follow-up: 680 · Valid Palindrome II, where you may delete one character.
• 9 · Palindrome Number (Easy) — Practice selection. Probing arithmetic reversal with the "solve it without converting to a string" constraint.

The escalation to expect on 5 and 647 is always the same: state the complexity, then be asked whether it can be beaten. Knowing that Manacher's exists and roughly why it works is worth far more than being able to type it.

Complexity

Expansion — time O(n²), O(1) working space plus the returned substring. There are 2n - 1 centres and each expansion walks outward at most n/2 steps, giving O(n) per centre. The worst case is a string of identical characters, where every centre expands to the boundary. Space is two integer pointers plus two integers for the best answer.

DP table — time O(n²), space O(n²). The n² storage cells are initialised; only the upper triangle is evaluated, with constant work per cell and a shorter interior dependency for lengths at least 3. The memory is the real cost: at n = 5000 that is 25 million list entries referencing boolean values, plus row overhead; compare that allocation with the memory budget.

Counting all palindromic substrings is the same O(n²) expansion, incrementing once per successful outward step rather than tracking a maximum. The count itself can be large but fits comfortably in a machine integer for the usual constraints.

You can now…

• Distinguish palindromic substring problems from subsequence problems by reading the noun, and pick expansion or grid accordingly.

• Write the expand helper cold, with the bounds guard before the character comparison.

• Return the correct half-open bounds, stepping back in on the left and not on the right.

• Drive both odd and even centres, and say why there are exactly 2n minus 1 of them.

• Turn the same driver into a counter for Palindromic Substrings by changing only the accumulator.

• Fill the boolean palindrome table in an order that never reads an unwritten cell — by length, or with i descending.

• Name Manacher's algorithm as the O(n) answer and sketch the mirror-reuse idea in two sentences.

Quiz

Self-check (answer follows each question).

Q: How many centres does a string of length n have, and why is it not n?

A: For n > 0, there are 2n - 1: n character centres and n - 1 internal gaps. The empty string has zero centres and this driver returns the empty string.

Q: After expand exits, why is the palindrome s\[l+1:r] rather than s\[l:r+1]?

A: The loop increments and decrements after a successful match, so on the final failing iteration the pointers have already moved one step beyond the last matching pair. l and r both sit outside the palindrome.

Q: Why does increasing substring length work, and is it the only valid fill order?

A: The interior dp[i+1][j-1] is shorter, so length-first computes it earlier. Descending i with ascending j also works. Increasing-i row-major order can read unfilled interiors; on "abcba", dp[0][4] needs dp[1][3] first.

Q: What input makes expand-around-centre hit its worst case?

A: A string of identical characters, such as n copies of 'a'. Every centre expands all the way to the string boundary, giving the full quadratic work.

Q: What is the one test case that proves you handled even-length palindromes?

A: Something like 'cbbd', where the answer is 'bb'. An implementation that only tries odd centres returns a single character.

Q: Longest Palindromic Subsequence is not solved by expansion. What is it, and why does the difference matter?

A: Its optimal length equals LCS(s, reversed(s)). Subsequences may skip characters, so contiguous centre expansion does not apply. This is a length reduction: an arbitrary LCS witness need not itself be palindromic; use an interval-LPS traceback if a palindrome witness is required.

Stretch: For minimum cuts, define pieces[0]=0 and pieces[end]=min(pieces[start]+1) over starts whose s[start:end] is palindromic. Return pieces[n]-1 for nonempty s, and 0 for empty s. On "aab", pieces is [0, 1, 1, 2], so one cut gives "aa" | "b". There are O(n²) candidate starts in total, not O(n) work.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

If the blank-file expand came out with the wrong return bounds, log it as failed even though the fix took ten seconds. The queue measures what you could retrieve cold.

• Every palindrome has exactly one centre, and there are 2n - 1 centres because gaps count.

• Expansion is O(n^2) time and O(1) space — same complexity as the table, far less machinery, no fill-order trap.

• The expansion loop overshoots by one on each side; the answer is s\[l+1:r].

• Counting all palindromic substrings is the same loop with a counter instead of a max — two lines different.

• Build the boolean table only when a backtracking search will query is-palindrome repeatedly, as in Palindrome Partitioning.

• If you build the table, iterate by substring length or descend the left endpoint. Increasing-left row-major order can read unfilled interiors.

Corrective source notes

• Manacher's Algorithm - Finding all sub-palindromes in O(N) - Algorithms for Competitive Programming — Manacher reuses palindrome symmetry to obtain linear-time palindrome-radius computation. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.