You need the longest palindrome in a string. Where does centre-expansion cost you, and what does it cost?

Short answer

For longest palindromic substring, expand around every character center and every gap between characters. There are 2n - 1 centers, each expansion can cost O(n), so center expansion is O(n squared) worst case and O(1) extra space. The worst case is a string of repeated characters, where most centers expand nearly to the boundary.

Settle which problem you were given

Palindromic substring and palindromic subsequence are different questions that sound identical when spoken. A substring is contiguous; a subsequence is not. In character, the longest palindromic substring is ara, three letters sitting next to each other, while the longest palindromic subsequence is carac at five, because it is allowed to step over the h.

They also have different algorithms. Subsequence is a two-index dynamic program, and it is the same computation as the longest common subsequence of the string and its reverse. Centre expansion has no meaning there, because a subsequence has no centre in the string.

Ask which one, in one sentence, then commit. Interviewers phrase this loosely, and candidates who assume have a fifty per cent chance of solving something nobody asked for.

Settle the tie-break too. Several palindromes may share the maximum length, and whether you return the first, the last, or any of them should be a decision rather than an accident of loop order.

Why the centre is the right thing to enumerate

A palindrome reads the same in both directions, which means it is symmetric about a middle. So rather than enumerating substrings, of which there are about n squared over two, you enumerate middles and grow each one as far as the symmetry holds. Each middle yields the longest palindrome centred there, and the answer is the best of them.

The count of middles is where answers go wrong. An odd-length palindrome is centred on a character, giving n candidates. An even-length palindrome is centred on the gap between two adjacent characters, giving n minus 1 more. Total 2n minus 1.

Miss the gaps and the algorithm is not slightly worse, it is wrong. On abba it examines four character centres, none of which expands at all, and returns a single letter. That input is the standard first test for exactly this reason.

private int start, best;   // best palindrome found so far

String longest(String s) {
    for (int i = 0; i < s.length(); i++) {
        expand(s, i, i);        // odd centre: one character
        expand(s, i, i + 1);    // even centre: the gap after it
    }
    return s.substring(start, start + best);
}

private void expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    int length = r - l - 1;     // l and r have both overshot by one
    if (length > best) { best = length; start = l + 1; }
}

The arithmetic after the loop is the other place implementations lose a character. Both pointers step past the last matching pair before the loop exits, so the palindrome runs from l + 1 to r - 1 inclusive, which is r - l - 1 characters. Deriving that from where the loop stopped, rather than remembering the formula, is what stops the off-by-one.

Two pointers move here, but they diverge from a fixed middle rather than tracking a window, so none of the monotone-boundary reasoning that makes sliding-window problems linear applies.

What it costs, and which input charges you

Each centre expands at most to the ends of the string, so the loop is O(n) and there are O(n) centres, giving O(n squared) time. Extra space is O(1): two indices and two integers, with the substring allocated once at the end.

That bound is a worst case, and naming the input that reaches it is the part of the answer an interviewer is listening for. Take a string of ten thousand identical characters. Every comparison inside every expansion succeeds, so each centre runs until it hits a boundary. The odd centre at position i expands by the smaller of i and n minus 1 minus i, and summing that over all positions gives roughly n squared over four, which is about twenty-five million character comparisons before the even centres are counted at all.

Now take a random string over the twenty-six letters. The chance that a given expansion survives even its first comparison is one in twenty-six, so almost every centre stops immediately and the total work is close to linear. Centre expansion is therefore data-dependent in a way the bound hides: it is quadratic on repetitive text and effectively linear on ordinary text.

That is a useful thing to say out loud, because it tells the interviewer you know when the worst case matters. Genomic sequences over four symbols, or a field padded with a repeated character, are exactly where it bites.

The table is not the improvement

Candidates who have seen the dynamic programming formulation often offer it as the better answer. It fills a boolean table where an entry says whether the substring between two indices is a palindrome, using the rule that a substring is a palindrome when its ends match and its interior already is.

It is O(n squared) time, the same as centre expansion, and O(n squared) space, which is worse. On a string of a hundred thousand characters that table is ten billion entries, so the approach is not merely inelegant, it fails to run. Offering it as an optimisation is a tell that the complexities were memorised as a pair rather than compared.

The table earns its place elsewhere. It is the natural base for counting all palindromic substrings, for partitioning a string into palindromes, and for any variant that needs repeated queries about arbitrary ranges, because it answers those in constant time once built.

What Manacher's method actually reuses

The linear-time algorithm is worth being able to describe even if you would not write it under time pressure, because the description is what shows understanding.

Keep track of the palindrome found so far that reaches furthest to the right, remembering its centre and its right edge. When you reach a new centre that lies inside that palindrome, its mirror position on the other side of the remembered centre has already been solved, and by symmetry the new centre's radius is at least the mirror's radius, capped at the distance to the remembered right edge. So you start expanding from that inherited radius rather than from zero.

The cost argument is the part to state. Every comparison that succeeds pushes the right edge further right, and the right edge only ever moves forward across the whole run, so successful comparisons total O(n). Every centre contributes at most one failed comparison. Linear overall.

The usual implementation first interleaves a separator between every pair of characters, which makes every palindrome odd-length and removes the parity branch entirely, at the cost of a working array of 2n plus 1 entries. That transformation is the trick worth remembering; the bookkeeping around the right edge is the part best looked up.

A middle option exists if the interviewer wants better than quadratic without Manacher. Because a palindrome of length L contains one of length L minus 2 with the same centre, existence is monotone within each parity, so you can binary search the length and test candidates with a rolling hash comparing each window against its reverse. That gives O(n log n) with a hash collision risk you have to acknowledge. It is more moving parts than Manacher for a worse bound, which is itself a reason to prefer Manacher, and knowing that is a better answer than knowing three algorithms.

Centre expansion is the right first answer, and the thing to say alongside it is that its quadratic case is reached by repetition rather than by length, because that is the sentence which decides whether it is good enough for the input you have.

---

© 2026 Preptima. Originally published at preptima.com.