skip to content

In expand-around-center palindrome search, why must you consider 2n-1 centers, not n?

level: middleimportance: must knowfreq 66%

answer

  1. palindromes come in two shapes
  2. where does an even-length one fold?
  3. not on a character at all
  4. count characters, then count the gaps
  5. n plus the boundaries between them

basics

~20 s

Palindromes come in odd and even lengths. Expanding from single characters only finds odd ones; an even-length palindrome is centred in the gap between two adjacent characters. That is n character centres plus n-1 gap centres, so 2n-1 in all.

solid answer

~40 s

Every palindrome has exactly one centre, but the centre is not always a character. Odd-length palindromes are centred on a character, so expanding outward from position `c` with both pointers starting at `c` finds them. Even-length palindromes have no middle character — their centre is the boundary between positions `c` and `c+1` — so you must also expand with the pointers starting one apart. A string of length n has n character positions and n-1 boundaries between them, giving 2n-1 centres. Each expansion costs at most O(n), so the whole scan is O(n^2) time with O(1) extra space. Skipping the gap centres is the classic bug: the scan then reports 1 for a string that is entirely symmetric in pairs, and no test on odd-length inputs will catch it.

code

pseudocode · 9 lines
pseudocode
best = 0
for c in 0..length(s)-1:
    lo = c
    hi = c
    while lo >= 0 and hi < length(s) and s[lo] == s[hi]:
        best = max(best, hi - lo + 1)
        lo = lo - 1
        hi = hi + 1
...

go deeper

for a junior

Be ready to say that palindromes can be odd or even in length and that the even ones fold between two characters. Counting n characters plus n-1 gaps is the recall you need.

for a middle

Explain the expansion loop, its O(n^2) worst case on a repeated character, and its O(1) extra space. Spot the missing even-centre pass when shown a plausible-looking scan.

for a senior

Demonstrate how you would catch this in review or testing: name an even-length input that exposes it, and note that odd-only test data passes while every even answer is silently truncated.

for a principal

Own the call between an easily understood quadratic scan and a linear algorithm that few on the team can maintain. Tie it to the real input lengths and the cost of a wrong symmetric-region report.

## The idea behind the method Instead of testing every one of the O(n^2) substrings for symmetry (which would cost another O(n) each, O(n^3) total), you turn the problem around: enumerate every possible **centre** of a palindrome and grow outward while the characters on both sides agree. The moment they disagree, no longer palindrome shares that centre, so you stop and move on. This is complete because every palindrome has exactly one centre. It is efficient because each centre's expansion stops early on real data. ## Why the centre count is 2n-1 A palindrome of **odd** length has a middle character: `GTG` is centred on the `T`. Grow from `lo = hi = c`. A palindrome of **even** length has no middle character: `AA` and `AACCAA` fold along a boundary that lies *between* two characters. Grow from `lo = c`, `hi = c+1`. For a string of length n there are: - n character positions -> n odd centres, - n-1 boundaries between neighbouring characters -> n-1 even centres, for a total of **2n-1**. A run of identical bases such as `AAAA` makes the point concrete: `AAA` is centred on a character, `AAAA` is centred on a gap, and both live in the same string. ## The bug this question is really about The fragment attached to this question loops over n centres only. On the marker string `AACCAA` — which is symmetric in full, length 6 — it reports **1**. Trace it: at every character centre the neighbours differ (`A` against `C`, `C` against `A`), so no expansion ever succeeds past width 1, and the pair centres that would catch `AA`, `CC` and the whole string are never visited. This failure mode is nasty for two reasons. First, the code looks finished: it has a centre loop, a two-pointer expansion and a running maximum. Second, it is *correct* on every odd-length answer, so a test suite built from examples such as `GTG` or `ACGTGCA` passes clean while every even-length answer is silently truncated. ## Boundaries worth stating out loud - **Empty input**: 2n-1 with n = 0 gives -1, i.e. no centres at all. The loop body never runs and the best length stays 0. Initialise the running best to 0, not 1, or you will claim a palindrome inside an empty string. - **Single character**: one centre, no gaps, answer 1. A string of length 1 is a palindrome. - **Two identical characters**: zero odd centres would suffice for length 1, but the single gap centre is what produces the correct answer of 2. ## Cost, honestly stated Each expansion walks outward at most n/2 steps, and there are 2n-1 centres, so the worst case is O(n^2) time. That worst case is real, not theoretical: a long run of one repeated base makes every centre expand nearly to the ends. The extra space is O(1) — two indices and a running best — which is the method's main attraction over an interval table. Note what O(n^2) does *not* say. It is an upper bound, and on ordinary sequence data most expansions stop after a step or two, so the observed cost is close to linear. Do not let that fool you into promising linear worst-case behaviour. ## The unification trick There is a well-known way to collapse the two cases: conceptually interleave a separator character that appears nowhere in the input between every pair of characters (and at both ends). Every palindrome in the transformed string then has odd length and a character centre, and the transformed length is 2n+1 — which is exactly where the 2n-1 real centres come from, plus the two useless ends. This transformation is the front half of the linear-time palindrome algorithm (Manacher's), which reuses previously computed radii instead of expanding each centre from scratch. For interview purposes, knowing why the transform exists is usually enough; reach for the linear algorithm only when the input is long enough that O(n^2) genuinely hurts. ## What a strong answer sounds like "Every palindrome has one centre, but even-length ones are centred between characters, so there are n plus n-1 centres. Expanding each is O(n) worst case, giving O(n^2) time and O(1) space. The classic bug is looping over n centres only — that silently caps you at odd-length answers, and a string like `AACCAA` returns 1."

  • What is the worst-case input for this scan, and what does it cost?
    A long run of one repeated character. Every centre then expands almost to both ends before failing, so the total work is quadratic in the length — O(n^2) time. On ordinary mixed data most expansions stop within a step or two, but the bound is genuinely reachable, not just theoretical.
  • Both centre expansion and an interval table are O(n^2) time — what does the table give you that centres do not?
    Random access. The table answers "is the stretch from i to j symmetric?" in constant time for any pair, which an enclosing computation can query many times — for example one that splits a read into the fewest symmetric pieces. Centre expansion produces one answer and keeps nothing.
  • What should the routine return for an empty input and for a single character?
    Zero and one. Start the running best at 0 so the empty case falls out naturally, since a zero-length string has no centres at all. A single character is a palindrome of length 1, produced by its own character centre with no expansion.

saying these in an interview costs you the question

  • Loops over n centres and calls it complete
  • Says even-length palindromes have a middle character
  • Claims centre expansion is linear time
  • Initialises the best length to 1, breaking empty input
  • Thinks the method needs extra space proportional to n

context

resolving links…