Palindromic substrings in Python: expanding around centres

Why this matters

A palindrome is a word or phrase that reads the same forwards and backwards. The word level is one. So is racecar. Interview questions often ask how many palindromes sit inside a longer string, because the answer needs a careful plan. A naive plan checks every piece of the string separately and wastes effort. This lesson shows a faster plan, expanding around each centre, and a second plan that uses a table. Both give the same answer, and the lesson checks that with real output.

Lesson 9 of this module covers word break, which also works on pieces of a string. This lesson does not repeat that. It focuses on palindromes.

By the end of this lesson you will be able to count and list palindromic substrings in Python, explain why there are 2n minus 1 centres, fill the palindrome table in the right order, and avoid the mistakes that give wrong counts or errors.

Terms, defined

• A palindrome reads the same from left to right and from right to left. A single letter is a palindrome. So is the empty string, but this lesson only counts pieces of length 1 or more.
• A substring is a piece of a string made of letters that sit next to each other. In abc, the pieces are a, b, c, ab, bc and abc.
• A palindromic substring is a substring that is a palindrome.
• A centre is the middle of a palindrome. An odd-length palindrome such as aba has a centre on a letter, the b. An even-length palindrome such as abba has a centre in a gap, between the two b letters.

One detail matters for the count. A substring is counted by where it sits, not by what it says. The string aa has three palindromic substrings: the first a, the second a, and aa. A set of distinct strings would give only two, a and aa. The task here counts positions, and the code counts positions.

Start with a single check

Before counting many pieces, check one string. Put one finger on the first letter and one on the last. If the two letters differ, the string is not a palindrome. If they match, move both fingers one step inward and repeat. When the fingers meet or cross, every pair matched, so the string is a palindrome.

For racecar, the pairs are r and r, then a and a, then c and c. The middle letter e is left alone. The answer is yes.

This check takes time proportional to the length of the string. Counting palindromes inside a string means doing this check for many pieces. The next idea makes that cheaper.

The idea: grow outward from a centre

Every palindrome has a centre, and the palindrome grows outward from it. If c is the centre letter of racecar, then e and c on each side match, then a and a, and so on. Start at a centre and grow outward one pair at a time. Each time the pair matches, a new palindrome has been found. When a pair does not match, stop. Nothing further out from that centre can be a palindrome.

Here is the tricky part. A string of n letters has 2n minus 1 possible centres. There are n centres on letters, one for each letter, because an odd-length palindrome has its centre on a letter. There are n minus 1 centres in gaps between letters, because an even-length palindrome has its centre between two letters. Together that is n plus n minus 1, which is 2n minus 1.

For abba, which has 4 letters, the centres look like this.

letters:   a   b   b   a
centre no: 0   2   4   6     (letter centres, even numbers)
gap no:      1   3   5       (gap centres, odd numbers)

The code uses the number i to find each centre. If i is even, the centre is the letter at i // 2, so the left and right positions are the same. If i is odd, the centre is the gap after letter i // 2, so the left position is i // 2 and the right position is one more.

left = i // 2
right = left + i % 2

The i % 2 part is 0 for even numbers and 1 for odd numbers. That is the whole trick for handling both kinds of palindrome in one loop. The symbol // is integer division, which drops the fraction, so 5 // 2 is 2.

Method 1: expanding around each centre

Here is the counting method. For each of the 2n minus 1 centres, expand while the two letters match and both positions are still inside the string.

def count_by_expanding(s):
    n = len(s)
    count = 0
    for i in range(2 * n - 1):
        left = i // 2
        right = left + i % 2
        while left >= 0 and right < n:
            if s[left] != s[right]:
                break
            count += 1
            left -= 1
            right += 1
    return count

The listing version is the same loop, but it records each palindrome as a range and its text. The range [left, right + 1) is written in the half-open style: it includes left and stops before right + 1. This matches how Python slices work, so s[left:right + 1] gives the text.

def list_by_expanding(s):
    n = len(s)
    found = []
    for i in range(2 * n - 1):
        left = i // 2
        right = left + i % 2
        while left >= 0 and right < n and s[left] == s[right]:
            found.append(f"[{left},{right + 1}) {s[left:right + 1]}")
            left -= 1
            right += 1
    return found

Worked example 1: abba step by step

Take abba. It has 4 letters and 7 centres. Here is what happens at each centre, with the pair that is compared and the result.

• Centre 0, on the first a. Pair (0, 0) matches. Found a. Next pair (-1, 1) is outside the string, so stop. Count is 1.
• Centre 1, the gap between a and b. Pair (0, 1) is a and b. No match. Count stays 1.
• Centre 2, on the first b. Pair (1, 1) matches. Found b. Next pair (0, 2) is a and b. No match. Count is 2.
• Centre 3, the gap between the two b letters. Pair (1, 2) is b and b. Found bb. Next pair (0, 3) is a and a. Found abba. Next pair (-1, 4) is outside. Count is 4.
• Centre 4, on the second b. Pair (2, 2) matches. Found b. Next pair (1, 3) is b and a. No match. Count is 5.
• Centre 5, the gap between the second b and the last a. Pair (2, 3) is b and a. No match.
• Centre 6, on the last a. Pair (3, 3) matches. Found a. Next pair (2, 4) is outside. Count is 6.

The final count is 6. Here is the real output from the program, which lists the palindromes in the order the centres were visited.

abba: expanding=6 table=6
  list: ['[0,1) a', '[1,2) b', '[1,3) bb', '[0,4) abba', '[2,3) b', '[3,4) a']

The order matches the trace above. The list does not come out sorted, so a test that compares lists should sort both first.

Worked example 2: a palindrome inside a palindrome

Take abcba. It has 5 letters and 9 centres. The string itself is a palindrome, and it contains a smaller palindrome bcb around the centre letter c.

The centre on c (position 2) finds c, then bcb (positions 1 to 3), then abcba (positions 0 to 4). Three palindromes come from one centre. The other centres find the single letters a, b, b and a, and nothing else, because each neighbour pair differs.

abcba: expanding=7 table=7
list for abcba: ['[0,1) a', '[1,2) b', '[2,3) c', '[1,4) bcb', '[0,5) abcba', '[3,4) b', '[4,5) a']

Count the list: 7 palindromes. The three from the centre on c appear as c, bcb and abcba, which are the 3rd, 4th and 5th entries in the list. The expansion does not stop at the first palindrome it finds. It keeps going while the pairs match, and that is why one centre can produce many answers.

Worked example 3: the same letter everywhere

Now take racecar, which is harder because the expansion from the middle centre reaches the whole string. It has 7 letters and 13 centres. The real output is:

racecar: expanding=10 table=10
list: ['[0,1) r', '[1,2) a', '[2,3) c', '[3,4) e', '[2,5) cec', '[1,6) aceca', '[0,7) racecar', '[4,5) c', '[5,6) a', '[6,7) r']

There are 7 single letters, and the three longer palindromes cec, aceca and racecar all come from the centre on e. That makes 10. Notice that the single letter e appears once, from the centre on e, and the expansion from that centre did not stop until it ran off both ends.

A string of only the same letter is the worst case for this method, because every centre expands as far as it can. The next section measures that case.

Method 2: the table of all ranges

The second method uses a table is_pal where is_pal[i][j] is true when the piece from position i to position j, inclusive, is a palindrome. It is simple to state. A range is a palindrome when its two end letters match and the range inside them is a palindrome. The inside range is one letter shorter on each side.

def palindrome_table(s):
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for length in range(2, n + 1):
        for i in range(0, n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                is_pal[i][j] = (length == 2) or is_pal[i + 1][j - 1]
    return is_pal

Every single letter is a palindrome, so the diagonal is_pal[i][i] starts as true. The rest is filled by length, from 2 up to n. For a range of length length that starts at i, the end is j = i + length - 1. The inside range is_pal[i + 1][j - 1] has length length - 2, which was filled in an earlier pass. For a range of length 2, the inside is empty, so the check is just whether the two letters match. The (length == 2) part handles that case.

The count is the number of true cells.

def count_by_table(s):
    t = palindrome_table(s)
    return sum(1 for row in t for b in row if b)

The next program prints the counts from both methods for a few words, and the first row of the table for abcba. It does not read input.

The output is:

abba: expanding=6 table=6
racecar: expanding=10 table=10
aa: expanding=3 table=3
aaa: expanding=6 table=6
aba: expanding=4 table=4
[True, False, False, False, True]

The last line is the first row of the table for abcba. It says the ranges [0,0] and [0,4] are palindromes. Range [0,0] is a. Range [0,4] is the whole string abcba. The other ranges that start at 0 are not palindromes.

Comparing the two methods

Both methods give the same count on every input the test tried. A check on 2000 random strings of up to 11 letters over a, b and c found no mismatch between the two methods. The random strings change with the seed, so this is a claim about one run. The code to write that test is short. Build it yourself and run it after any change to the palindrome code.

The work comparison uses strings made of one repeated letter. The counts below come from a Python run that counts each letter comparison. The expansion count adds 1 for each comparison made inside the while loop while both positions are inside the string. The table count adds 1 for each pair of positions that is at least 1 apart.

all a, n=100: palindromes=5050 (5050) comparisons expanding=5050 table=4950
all a, n=200: palindromes=20100 (20100) comparisons expanding=20100 table=19900
all a, n=400: palindromes=80200 (80200) comparisons expanding=80200 table=79800

The number of palindromes in a string of n identical letters is n times n plus 1, divided by 2. For 100 letters that is 5050, which matches. The comparison counts are close but not the same. The table makes one comparison for each pair of positions i and j with j - i at least 1, which is n times n minus 1, divided by 2. The expansion method makes one successful comparison for each palindrome it finds, plus one failed comparison for each centre that stops on a mismatch. It stops without a comparison when it runs off the end of the string.

The memory is the bigger difference. The table has n times n cells, so a string of 400 letters needs 160,000 cells, even though only the upper half is used. The expansion method keeps only the count and the list. It needs no table.

Expansion is also a good choice on ordinary text. Most centres stop after one or two comparisons when neighbouring letters differ. That is a reasoning claim, not a measurement made in this lesson. The worst case for both methods is still about n squared work.

Common mistakes

Only checking odd-length centres. A beginner often writes the loop with left = i and right = i for every i in range(n). That finds odd-length palindromes only. For aa it finds two palindromes, the two single letters, and misses aa, so the count is 2 where the correct count is 3. The fix is the i // 2 and i % 2 pair shown above, which also covers the gaps.

Forgetting the bounds check. The while loop must stop when left drops below 0 or right reaches the end. Python does not stop a negative index. It counts from the end of the string, so a missing check gives a wrong answer with no error. The next program removes the check for left and prints 9 for aaa, where the correct count is 6.

The output is without the left check: 9. When left becomes -1, the code reads s[-1], which is the last letter, and it keeps counting. The fix is to test left >= 0 and right < n before reading the letters, as the code above does. If the right check is missing instead, Python stops with IndexError: string index out of range.

Forgetting the length-2 case in the table. When length is 2, the inside range is_pal[i + 1][j - 1] is empty, and j - 1 is smaller than i + 1. A buggy version reads a cell that was never set, which is False, and so misses every pair of equal letters. The next program runs that version on aa.

The output is bad count for aa: 2, and the correct count is 3. No error is raised, so the wrong count can pass unnoticed. Test with aa and aaa whenever you change palindrome code.

Counting distinct strings instead of positions. A set of the palindrome texts removes repeats. For aaa there are 6 positional palindromes but only 3 distinct texts, a, aa and aaa. The count method here counts positions, which matches the usual definition of the problem. Check which one the question asks for before you write the code.

Filling the table in the wrong order. The cell is_pal[i][j] needs is_pal[i + 1][j - 1]. If the loops fill i from 0 upward and j from i upward, the inner cell may not be filled yet, and it reads False. Filling by length guarantees the inside is always done first.

Practice

Try each exercise before reading its answer.

Exercise 1. Count the palindromic substrings of level by hand, and list them.

Show the answer

The count is 7. The palindromes are l, e, v, e, l, eve and level.

Exercise 2. How many centres does aaaa have, and how many palindromic substrings does it have?

Show the answer

It has 7 centres, because 2 times 4 minus 1 is 7. It has 10 palindromic substrings. Four are single letters, three are length 2, two are length 3, and one is the whole string.

Exercise 3. The table method is run on aaaa. How many letter comparisons does it make, counting only ranges of length 2 or more?

Show the answer

It makes 6 comparisons. There are 3 pairs of length 2, 2 pairs of length 3 and 1 pair of length 4, which is 6 in total.

Exercise 4. The expansion method is run on aba. Write the list in the order the centres are visited.

Show the answer

The list is [0,1) a, [1,2) b, [0,3) aba, [2,3) a. Centre 0 gives a. Centre 1 is the gap between a and b, so it fails at once. Centre 2 is on b. It gives b, then grows to aba, then stops at the edge. Centre 3 is the gap between b and a, which fails. Centre 4 is on the last a, which gives a. The count is 4. Exercise 5. Why does the table version set is_pal[i][j] with (length == 2) or is_pal[i + 1][j - 1] and not just is_pal[i + 1][j - 1]?

Show the answer

For a range of length 2, the inside range is empty, and its index j - 1 is less than i + 1. The table has no meaningful value there, so the check must not rely on it. A range of length 2 is a palindrome exactly when its two letters match, and the length == 2 part says so directly.

Summary

• A palindrome has a centre, and it grows outward from there, one matching pair at a time.
• A string of n letters has 2n minus 1 centres. The i // 2 and i % 2 trick covers letter centres and gap centres in one loop.
• Expanding around centres counts and lists palindromes with no table, and it stops early when letters differ.
• The table method fills is_pal[i][j] by length, using the inside range that is already known. It uses about n squared cells of memory.
• Both methods agree on random tests, and both do about n squared work on a string of one repeated letter.