Palindromes: expand or table

46 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Take the word babad. A palindrome reads the same forwards and backwards, like bab or aba. Asked for the longest palindrome inside babad, a person would probably list every piece of the word and read each one backwards: b, ba, bab, baba, babad, then a, ab, and so on.

Count that work. A word of length n has about n²/2 pieces, and reading one backwards costs up to n comparisons. For babad that is 15 pieces and roughly 40 comparisons, which is fine. For a string of 1,000 characters it is about 500,000 pieces and 500 million comparisons. The waste is obvious once you notice it: when you check babad you compare a with a in the middle again, even though you already learned that aba is a palindrome.

Build the structure, one piece at a time

The structure here is not a stack or a tree. It is a way of growing an answer from the middle. Every palindrome has a centre. bab is centred on the a; abba is centred on the gap between the two bs. So there are two kinds of centre: a letter, or a gap between two letters. A string of length n has n letter centres and n − 1 gap centres, 2n − 1 in all. For babad that is 9 centres.

From a centre, grow outwards one step at a time. Keep two fingers, l on the left and r on the right. While the letters under the fingers match, move both fingers one step further apart. The moment they differ, or a finger falls off the end, stop: the last matching stretch is the longest palindrome with that centre.

1. Centre at index 1 (a): l = r = 1. One letter is always a palindrome, length 1.
2. Step out: l = 0, r = 2. s[0] = b, s[2] = b. They match, so bab is a palindrome, length 3.
3. Step out again: l = −1. Off the edge, stop. Best from this centre: bab.
4. Centre at index 2 (b): grows to aba, then meets b against d and stops.
5. Gap centres, such as between indices 0 and 1: b against a, no match, length 0.

The longest stretch found anywhere is the answer: bab (or aba, both length 3).

There is a second, table-based way to say the same thing. Keep a grid dp[i][j] that is true when s[i..j] is a palindrome. A single letter is true. A two-letter piece is true when the letters are equal. Anything longer is true exactly when its two end letters match and the inside piece dp[i+1][j−1] is already true. Fill the grid by length, short pieces first, so the inside is always known before you need it.

Why it is correct

Every palindrome has exactly one centre, so checking all 2n − 1 centres cannot miss one. Growing from a centre is safe because of one fact: if s[l..r] is a palindrome and s[l−1] = s[r+1], then s[l−1..r+1] is a palindrome too. Reading it backwards, the new outer letters match each other and the inside already reads the same both ways. The moment the outer letters differ, no wider piece with this centre can be a palindrome, because that mismatched pair stays inside every wider piece.

dp[i][j] = (s[i] = s[j]) and dp[i+1][j−1]

Why it is fast

There are 2n − 1 centres. From one centre the fingers can take at most n/2 steps before falling off an end, so one centre costs O(n). Altogether that is at most (2n − 1) × n/2, which is O(n²) comparisons, with no extra memory beyond two indices. The by-hand method was O(n³): a factor of n slower, because it kept re-reading the middle. The table method is also O(n²) in time but needs an n × n grid of booleans; it earns that memory when a problem asks the palindrome question many times, such as cutting a string into the fewest palindromic pieces.

How to recognise it in an interview

Listen for the words palindrome, substring and longest or count. Say out loud: every palindrome has a centre, so I will expand from each of the 2n − 1 centres. In Longest Palindromic Substring that sentence is the whole solution. In Palindromic Substrings, count one for every successful expansion step instead of keeping the longest. In Palindrome Partitioning the grid version pays off: build dp[i][j] once, then a second search only asks the grid, never re-reads the string.

02The idea in one line

Expand around each centre, or dp[i][j] = s[i]==s[j] and dp[i+1][j−1].

Reach for it when: Longest palindromic substring/subsequence, count palindromic substrings, partitioning.

Cost: O(n²) time.

03The walk-through, step by step

The video works one example: Longest Palindromic Substring on 'babad'. These are its captions in order, so you can follow without the video or check a step you missed.

1. Every palindrome has a centre: expand outward while the ends match
2. Centre 0 ('b'): a single letter is a palindrome
3. Hit the edge: stop
4. Centre 1 ('a'): a single letter is a palindrome
5. s[0] = s[2] = 'b': expand to 'bab'
6. Centre 2 ('b'): a single letter is a palindrome
7. s[1] = s[3] = 'a': expand to 'aba'
8. s[0] = 'b' ≠ s[4] = 'd': stop
9. Centre 3 ('a'): a single letter is a palindrome
10. s[2] = 'b' ≠ s[4] = 'd': stop
11. Centre 4 ('d'): a single letter is a palindrome
12. Hit the edge: stop
13. Even centres (between letters) found nothing; answer 'bab' (or 'aba')
14. 2n−1 centres, each expands O(n): O(n²), O(1) space

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).