L41 · DP IX — Palindromes

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

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. In practice one of them you can write correctly in ninety seconds under pressure and the other you cannot. That gap is the entire point.

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]

Two centres per index, 2n - 1 centres in total (the last even centre is out of range and the bounds check discards it harmlessly). Each expansion is O(n) worst case, so the whole thing is O(n²) time and O(1) extra space.

The DP table for comparison — same complexity, more machinery:

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):             # MUST grow by length
        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. Skip it and the table is quietly wrong.

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 interviews.
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 one is found in time proportional to its own length rather than by a separate scan.

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 nothing 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.

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 linear DP on top of the same table and is a good test of whether you can layer two DPs without confusing their indices.

Common failure modes

Off-by-one on the returned bounds. Returning (l, r) instead of (l+1, r) from the expansion. The reported palindrome is two characters too wide and includes the mismatching pair. It fails immediately on any input, which is at least merciful.

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 allocates O(n) each time and turns an O(n²) algorithm into something meaningfully slower. 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.

Complexity

Expansion — time O(n²), space O(1). 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²). Every one of the n² cells is computed once in constant time from a single already-filled neighbour. The memory is the real cost: at n = 5000 that is 25 million booleans, which in Python as a list of lists is far heavier than you want.

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.

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.