cf.completefrontend
STRING ALGORITHMS · CORE

Expand around the center

Find palindromes by starting at every middle point and growing outward while both sides match.

Time O(n^2)Space O(1)5 practice problemsStep-through picture

The idea

A palindrome is text that reads the same forward and backward, like level or abba. Every palindrome has a middle. For level the middle is the letter v. For abba the middle sits between the two b letters.

So instead of checking every possible piece of text, pick each possible middle and grow outward. Put a left pointer and a right pointer at the middle. While the characters under them are equal, move left one step left and right one step right. When they differ, or you hit an edge, the palindrome around that middle is as big as it gets.

A text of length n has 2n - 1 middles: n on letters (odd-length palindromes) and n - 1 between letters (even-length ones). Trying them all finds the longest palindrome in O(n^2) time with no extra memory.

An everyday example

Folding a paper strip

Write a word on a long paper strip and fold it at some point. Look at the letters that land on top of each other, starting next to the fold and moving outward. As long as each pair matches, the folded part reads the same both ways. The first pair that doesn't match tells you how far the mirror goes. You try a fold at every letter and between every two letters, and keep the longest mirror you saw.

How the example maps to the code
In the exampleIn the code
Where you fold the stripcenter, giving the start of left and right
A fold on a letter or between two letterscenter % 2 is 0 or 1
Checking the next pair outwardtext[left] === text[right], then left-- and right++
The first pair that doesn't matchThe while loop stops
The longest mirror so farbestStart and bestLength

From the slow way to expand around the center

  1. The most obvious way checks every substring. There are about n^2 / 2 substrings, and checking one takes up to n steps, so it costs O(n^3). For 1,000 characters that's hundreds of millions of steps.
  2. Much of that work repeats. If ollo is a palindrome, checking lollo needs only one more comparison: its outer pair, l and o, which differ. Every palindrome is a smaller palindrome with one matching pair added around it, so palindromes that share a middle can be checked together.
  3. So organize the search by middle instead of by substring. A middle is a letter, for odd lengths, or the gap between two letters, for even lengths. From each middle, grow outward one pair at a time while the pair matches. The first mismatch ends every palindrome with that middle, because any longer one would contain that same bad pair.
  4. To visit all 2n - 1 middles with one loop, number them with center: even numbers sit on letters and odd numbers on gaps, and left = Math.floor(center / 2) with right = left + (center % 2) turns the number into two pointers. Grow, measure right - left - 1, keep the longest: that loop is expand around the center.

How it works

  1. Keep the best palindrome found so far as bestStart and bestLength, both starting at 0.
  2. Loop center from 0 to 2 * text.length - 2. Even values sit on a letter and odd values sit between two letters.
  3. Set left = Math.floor(center / 2) and right = left + (center % 2). For a letter they are equal; between letters right is one more.
  4. While both pointers are inside the text and text[left] === text[right], move left one step left and right one step right.
  5. When the loop stops, the palindrome is the text strictly between left and right. Its length is right - left - 1.
  6. If that length beats bestLength, save bestStart = left + 1 and the new length.
  7. After all centers, return text.slice(bestStart, bestStart + bestLength).

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function longestPalindrome(text) {
  2. let bestStart = 0;
  3. let bestLength = 0;
  4. for (let center = 0; center < 2 * text.length - 1; center++) {
  5. let left = Math.floor(center / 2);
  6. let right = left + (center % 2);
  7. while (left >= 0 && right < text.length && text[left] === text[right]) {
  8. left--;
  9. right++;
  10. }
  11. const length = right - left - 1;
  12. if (length > bestLength) {
  13. bestStart = left + 1;
  14. bestLength = length;
  15. }
  16. }
  17. return text.slice(bestStart, bestStart + bestLength);
  18. }

How fast it is

TimeO(n^2)
Extra memoryO(1)

There are about 2n centers and each can grow up to n / 2 steps. Only a handful of numbers are stored.

  • Best caseO(n)

    No letter repeats near itself, like abcdef: each letter's center grows once and each gap stops at once. The loop grows 6 times for 6 letters.

  • Average caseO(n)

    Ordinary words and random text: most centers stop after one or two steps, so the run is close to linear even though the bound is O(n^2).

  • Worst caseO(n^2)

    One letter repeated, like aaaaaaaa: centers near the middle grow about n / 2 steps each. For 8 letters the inner loop grows 36 times, and in general about n^2 / 2 times.

Common mistakes

  • Only trying centers on letters. Even-length palindromes like abba have their middle between two letters and get missed.
  • Reading text[left] before checking left >= 0. JavaScript returns undefined instead of failing, which hides the bug until two undefined values compare equal.
  • Computing the length as right - left + 1. When the loop stops, both pointers are one step past the palindrome, so the length is right - left - 1.
  • Building a new substring at every step with slice. It works but adds needless copying; keep numbers and slice once at the end.

When to use it

Look for these clues in a problem:

  • The question mentions palindromes, mirrored text, or reading the same both ways.
  • You need the longest such piece, or a count of all of them.
  • The text is up to a few thousand characters, so O(n^2) time is fine.
  • You want an answer with O(1) extra memory and no table.

Check yourself

Answer each one in your head first, then open it.

How many centers does a text of 10 letters have?

19: 10 on letters and 9 on gaps, which is 2n - 1.

Why is the length right - left - 1 and not right - left + 1?

When the loop stops, left and right are both one step outside the palindrome. It runs from left + 1 to right - 1, which is right - left - 1 letters.

Why does the code return lol for lollipop, and not pop?

Both have length 3. The test is length > bestLength, so a later tie never replaces the first answer.

Why can growing stop for good at the first pair that doesn't match?

Any longer palindrome with the same middle would contain that same pair at the same mirrored positions, and those letters differ. So no longer palindrome with this middle exists.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Every palindrome has exactly one middle: its center letter if its length is odd, or the gap between its two center letters if its length is even. The loop visits all 2n - 1 middles, so the middle of every palindrome is tried exactly once.

From a middle, the while loop keeps one rule: the text strictly between left and right is a palindrome. That's true at the start, where it is empty for a gap, or is about to be a single letter. Each step adds one matching pair around it. When a pair doesn't match or a pointer leaves the text, no longer palindrome has this middle, because it would contain that same pair. So the loop stops at the longest palindrome for this middle.

The longest palindrome in the text is the longest one for its own middle, so it's measured when that middle is tried. bestLength keeps the largest length seen, and bestStart = left + 1 records where it begins, because left stops one step before it. After every middle has been tried, text.slice(bestStart, bestStart + bestLength) is the answer.

Going deeper

3 more ideas

Why every palindrome is found

Any palindrome has exactly one middle: a letter if its length is odd, or a gap between two letters if it is even. The loop tries every letter and every gap. From the right middle, growing outward checks the pairs of the palindrome one by one, so it reaches at least that palindrome before stopping.

How fast it is

There are 2n - 1 centers. Each one can grow up to about n / 2 steps, so the worst case is O(n^2), for example on aaaaaaa where every center grows far. On normal text most centers stop after one or two steps, so it runs much faster. It uses only a few number variables, so the extra memory is O(1).

Counting palindromes instead

Each successful step of the while loop finds one more palindrome around that center. To count all palindromic pieces, add 1 to a counter inside the loop instead of tracking the longest. The same 2n - 1 centers cover every piece exactly once.

Work it by hand

Every step in a table, with why

Find the longest palindrome in an 8-letter word that has two palindromes of the same best length.

text = "lollipop"

StepcenterStart left, rightStop left, rightlengthbestStart, bestLengthWhat happensWhy
100, 0-1, 110, 1l: new bestA letter always matches itself, so every odd center grows at least once. left then falls off the start.
210, 10, 100, 1l vs o: no growthThe gap between l and o holds no palindrome.
321, 1-1, 330, 3lol: new bestIt grows twice: o matches itself, then l and l match. left falls off the start.
431, 21, 200, 3o vs lNo growth.
542, 21, 310, 3l, then o vs lOnly the single letter.
652, 31, 420, 3ll: too shortAn even palindrome: l and l match, then o and i differ. Length 2 doesn't beat 3.
763, 32, 410, 3lOnly the single letter.
873, 43, 400, 3l vs iNo growth.
984, 43, 510, 3iOnly the single letter.
1094, 54, 500, 3i vs pNo growth.
11105, 54, 610, 3pOnly the single letter.
12115, 65, 600, 3p vs oNo growth.
13126, 64, 830, 3pop: a tie, not keptpop also has length 3, but 3 > 3 is false, so the first palindrome found keeps its place. right falls off the end.
14136, 76, 700, 3o vs pNo growth.
15147, 76, 810, 3pThe last center, 2 * 8 - 2. The loop ends.

It returns text.slice(0, 3), which is lol. All 15 centers were tried, and the inner while loop grew 11 times in total.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Expand around the centerO(n^2)O(1)Texts up to a few thousand characters, and interviews: short code with no extra memory.
Manacher's algorithmO(n)O(n)Very long texts, or when you need every center's radius for many questions.
Dynamic programming tableO(n^2)O(n^2)You need to answer "is this piece a palindrome?" for many pieces later; the table stores every answer.
Check every substringO(n^3)O(1)Only as the slow starting point, or to test a faster version on tiny inputs.

Extra memory: O(1): a few numbers, bestStart, bestLength, left, and right. Only the final slice makes a new string.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Expand around the center and the other approaches, on a scale where each line up is 10 times more steps.
  • Expand around the center, Dynamic programming table O(n^2)
  • Manacher's algorithm O(n)
  • Check every substring O(n^3)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Expand around the center1001 million1 trillion
Manacher's algorithm101,0001 million
Dynamic programming table1001 million1 trillion
Check every substring1,0001 billionmore than a quadrillion

Inputs that need care

5 tricky inputs
Empty text: ""
2 * 0 - 1 is -1, so the loop never runs, and text.slice(0, 0) returns "".
One letter: "q"
There is one center. It grows once, so it returns q.
No repeated letters: "abcd"
Every palindrome has length 1. The first one, a, is kept, because later ties don't pass length > bestLength.
The whole text is a palindrome: "redder"
The gap between the two d letters grows until both pointers leave the text, at left = -1 and right = 6, so it returns redder.
Mixed case: "Abba"
A and a are different characters, so it returns bb. Lowercase a copy first if case shouldn't matter, and slice the original text with the same indexes.

Variations and follow-ups

Twists interviewers add

Longest palindrome at the start

To find the fewest letters to add in front of a text to make it a palindrome, you need the longest palindrome that starts at index 0. Expanding works in O(n^2). KMP's table built on text + "#" + reversed text gives it in O(n): its last value is that palindrome's length.

A palindrome after removing one letter

To check whether deleting at most one letter makes the text a palindrome, walk two pointers in from the ends. At the first mismatch, try skipping the left letter or the right one, and check the rest normally. That is O(n).

Manacher's algorithm

It visits the same centers, but reuses what a big palindrome already says about its mirror image. Each comparison that succeeds pushes a boundary forward, so all centers together take O(n).

Longest palindromic subsequence

If the letters don't have to be next to each other, it's a different problem. Dynamic programming over left and right solves it in O(n^2) time.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "longest palindromic substring", "count palindromic substrings", or any question about pieces that read the same both ways. Pieces made of neighboring letters point to centers; letters that may be skipped point to dynamic programming.
  • Name the two kinds of middles before coding: letters for odd lengths and gaps for even lengths. Forgetting the gaps is the most common bug, and naming it early shows you know.
  • Use a helper called twice per index, or the center numbering trick; both are fine. Say the length formula right - left - 1 and why: both pointers stop one step past the palindrome.
  • Test by hand: one letter, an even palindrome like abba, and a text with no palindrome longer than 1. The usual follow-up is "can you do better than O(n^2)?": Manacher's algorithm does it in O(n).

Where frontend code uses it

The same idea in real UI code
  • Double-clicking a word in a text field selects it by growing outward from the click point while the next characters still belong to the word. That is the same outward growth with a different stop rule.
  • Code editors that expand a selection step by step (for example to the word, then the quotes, then the brackets) also grow a left and right edge outward from the cursor.
  • The inner two-pointer check is what you would use to validate input that must read the same both ways, such as a palindrome puzzle in a word game.

Related algorithms