Search & scan · pattern 5 of 7

Expand around a center

A palindrome is a piece that reads the same forward and backward. Take away its two ends and the rest is still one. So start at a middle, called a center, and grow outward one step on each side while the ends match.

Watch it run in the app

When to use it

Use it when the pieces you want read the same from both ends and may sit anywhere in the input, so their two ends are not known in advance.

It belongs to the search & scan group: Move one or two positions across the input so that nothing is looked at more than a few times.

Watch it work

A game lays number tiles in a row. You may take one run of neighboring tiles that reads the same from both ends, such as 3, 5, 3 or one tile alone. Your score is the sum of its tiles. Return the highest score you can get.

Input
tiles = [3, 5, 3, 8, 8]

Output
16

The method

Keep the best score so far
Try each center in turn: one tile, then that tile and the next
While both ends are inside the row and match
Add the ends to the score and keep the best score
Move both ends one tile outward
Return the best score

The run, one moment at a time

Step 1. No center has been tried yet, so the best score is 0.
```
tiles: 3 5 3 8 8
best: 0
```
Step 2. The first center is one tile, tile 0. Left and right both start on it.
```
tiles: 3 5 3 8 8  (both at 0)
score: 0
best: 0
```
Step 4. A tile always matches itself, so add it once: score 3, the new best. One step outward, left is off the row, so this center stops.
```
tiles: 3 5 3 8 8  (both at 0)
score: 3
best: 3
```
Step 3. Center on tiles 0 and 1: 3 and 5 differ, so no palindrome starts here.
```
tiles: 3 5 3 8 8  (left at 0, right at 1)
score: 0
best: 3
```
Step 5. Center on tile 1 alone: score 5, the new best. Now move both ends one tile outward, to tiles 0 and 2.
```
tiles: 3 5 3 8 8  (left at 0, right at 2)
score: 5
best: 5
```
Step 4. 3 and 3 match, so 3, 5, 3 is a palindrome. Add both: score 11, the new best. One step outward, left is off the row, so it stops.
```
tiles: 3 5 3 8 8  (left at 0, right at 2)
score: 11
best: 11
```
Step 3. Center on tiles 1 and 2: 5 and 3 differ, so no palindrome starts here.
```
tiles: 3 5 3 8 8  (left at 1, right at 2)
score: 0
best: 11
```
Step 3. Center on tile 2 alone: score 3. One step outward, 5 and 8 differ, so it stops.
```
tiles: 3 5 3 8 8  (left at 1, right at 3)
score: 3
best: 11
```
Step 3. Center on tiles 2 and 3: 3 and 8 differ, so no palindrome starts here.
```
tiles: 3 5 3 8 8  (left at 2, right at 3)
score: 0
best: 11
```
Step 3. Center on tile 3 alone: score 8. One step outward, 3 and 8 differ, so it stops.
```
tiles: 3 5 3 8 8  (left at 2, right at 4)
score: 8
best: 11
```
Step 4. Center on tiles 3 and 4: 8 and 8 match, so 8, 8 is a palindrome. Add both: score 16, the new best. One step outward, right is off the row, so it stops.
```
tiles: 3 5 3 8 8  (left at 3, right at 4)
score: 16
best: 16
```
Step 3. Center on tile 4 alone: score 8. One step outward, right is off the row, so it stops.
```
tiles: 3 5 3 8 8  (left at 3)
score: 8
best: 16
```
Step 6. Every center has been tried. The best score is 16, from tiles 3 and 4.
```
tiles: 3 5 3 8 8
best: 16
```

The code

The numbered comments are the steps of the method.

JavaScript

function solve(tiles) {
  // 1. Keep the best score so far
  let best = 0;
  // 2. Try each center in turn: one tile, then that tile and the next
  for (let i = 0; i < tiles.length; i++) {
    for (const offset of [0, 1]) {
      let left = i;
      let right = i + offset;
      let score = 0;
      // 3. While both ends are inside the row and match
      while (
        left >= 0 &&
        right < tiles.length &&
        tiles[left] === tiles[right]
      ) {
        // 4. Add the ends to the score and keep the best score
        score += tiles[left];
        // One tile alone is both ends: it is added once.
        if (left < right) score += tiles[right];
        best = Math.max(best, score);
        // 5. Move both ends one tile outward
        left -= 1;
        right += 1;
      }
    }
  }
  // 6. Return the best score
  return best;
}

Python

def solve(tiles):
    # 1. Keep the best score so far
    best = 0
    # 2. Try each center in turn: one tile, then that tile and the next
    for i in range(len(tiles)):
        for offset in (0, 1):
            left = i
            right = i + offset
            score = 0
            # 3. While both ends are inside the row and match
            while (
                left >= 0
                and right < len(tiles)
                and tiles[left] == tiles[right]
            ):
                # 4. Add the ends to the score and keep the best score
                score += tiles[left]
                # One tile alone is both ends: it is added once.
                if left < right:
                    score += tiles[right]
                best = max(best, score)
                # 5. Move both ends one tile outward
                left -= 1
                right += 1
    # 6. Return the best score
    return best

How to spot it

Asked: The longest palindrome inside a string: Every palindrome has a middle. Growing outward from each middle finds the longest one around it, and the longest of those is the answer.
Asked: How many substrings are palindromes?: Each step outward that still matches is one more palindrome. Count the steps over all middles and none is missed or counted twice.
Given: The palindrome is a substring: its characters sit next to each other: With no gaps allowed, the two ends move away from one middle together. If characters may be skipped, there is no single middle to grow from.
Limits: Palindromes in a string of at most 1,000 characters: About 2,000 middles, each grown at most 500 steps, is at most a million comparisons. Testing every substring on its own can take about 83 million.

Looks like it, but is not

You must say whether the whole string is a palindrome. Use Opposing two pointers. The piece is known: the whole string. Start at its two ends and walk inward. There is no middle to search for.
The palindrome may skip characters: you delete some and keep the rest in order. Use Interval dynamic programming. With gaps, the two ends do not move apart together from one middle. You need a table of answers for every stretch, filled from short stretches to long ones.
You need the longest run of neighbors that obeys a rule, such as no character twice. Use Variable sliding window. That rule is about what the run holds, not about its two ends matching. Grow it on the right and shrink it on the left.

Cost and mistakes

With n tiles there are about 2n centers, and each can grow at most about n / 2 times. So time is at most about n × n steps, written O(n²). Extra space is a few numbers, written O(1).

Watch out

Try both kinds of center. A palindrome of even length, such as 8, 8, has no middle tile: its center is two tiles side by side. If you try single tiles only, every even one is missed.
Check that both ends are inside the row before you compare them. In Python, position -1 is the last item, so a missing check compares with the wrong tile and gives no error.

In the 150

2 problems of the 150 use it. Naming them gives their method away, so the list is folded.

Show the 2

Longest Palindromic SubstringMedium · 1-D Dynamic Programming
Palindromic SubstringsMedium · 1-D Dynamic Programming