In expand-around-center symmetry checks, why are there 2n-1 centers rather than n?

## The idea A symmetric span is a stretch of the sequence that reads the same in both directions. Instead of testing every stretch independently, expand-around-center fixes the **mirror line** and grows outward: put one index just left of the line and one just right, and while the two characters match, step both away from the line. When they stop matching, or an index leaves the sequence, the widest symmetric span around that line has been found. The payoff is that a span of length L is discovered in O(L) work rather than O(L) work *per candidate span*, and the whole thing needs only O(1) extra space — two indices and a length. ## Where the mirror line lives Here is the part interviewers actually probe. Consider a span of odd length: it has a genuine middle character, and the mirror line runs *through* that character. Now consider a span of even length: there is no middle element at all; the mirror line runs *between* two adjacent characters, and the innermost matching pair is those two neighbours. So the set of possible mirror lines over n characters is: - **n on-character centers** — one per index, seeding an expansion with `lo = hi = c`, which starts from a span of length 1; - **n-1 gap centers** — one per adjacent pair, seeding an expansion with `lo = c`, `hi = c + 1`, which starts from a candidate span of length 2 that only survives if those two characters match. Total: `n + (n-1) = 2n-1`. There are only n-1 gaps, not n, because the gaps before the first and after the last character cannot contain a non-empty span. **The bug this explains.** A loop that iterates `for c in 0..n-1` and seeds only `lo = hi = c` finds every odd-length symmetric span and no even-length one. It is a nasty bug because it does not crash and it is not obviously wrong on the inputs people try first — a lot of short hand-picked test inputs happen to have odd-length symmetry. The test that exposes it is any input whose only symmetric stretch is a repeated adjacent pair. ## Reading the bounds after the loop ``` lo = c hi = c while lo >= 0 and hi < n and s[lo] == s[hi]: lo = lo - 1 hi = hi + 1 span = hi - lo - 1 ``` The loop exits *after* the step that failed, so `lo` and `hi` are one position beyond the last confirmed match on each side. The widest valid span is therefore `[lo+1, hi-1]`, of length `(hi-1) - (lo+1) + 1 = hi - lo - 1`. Reading the bounds as `[lo, hi]` is the second most common defect here, and it is easy to check: seed at a single character in a sequence with no other match, and the expression must yield 1. Note also that the boundary conditions `lo >= 0` and `hi < n` must be evaluated *before* the character comparison, or the expansion indexes outside the sequence at the ends. ## Cost Each expansion runs until it fails or hits an edge, at most O(n) steps. Across 2n-1 centers that is O(n^2) time in the worst case — and the worst case is real, not theoretical: an input of one repeated character makes every expansion run all the way to the edges. On typical inputs expansions die quickly, so the measured cost is far below the bound; big-O is an upper bound, and an O(n^2) label does not claim the algorithm exhibits quadratic behaviour on ordinary data. Space stays O(1), because nothing is stored beyond a few indices — that is the technique's main attraction over table-based alternatives. ## What interviewers listen for The distinction between an on-character and an in-gap mirror line, stated before being prompted; the arithmetic `n + (n-1)`; the off-by-one after the loop justified rather than memorised; and an honest worst case with the input that triggers it. A candidate who says "you loop over every index" and stops there has just described a check that cannot see half of all symmetric spans.