Palindromic substrings: expanding around centres

Why this matters

Text problems often ask about patterns inside a string. A spell checker might flag repeated letters. A DNA reader might look for stretches that read the same both ways. A word game might score words that are palindromes. In each case you need to find every piece of the string with a certain shape, not just one piece.

A palindrome is a piece of text that reads the same from left to right and from right to left. This lesson counts all the palindromic pieces of a string and lists them. It uses a method called expanding around centres, which is simple to write and needs almost no extra memory. Then it compares that method with a table method that stores one answer for every pair of positions. The table method is a dynamic programming method, so it uses the same idea as the memoization lesson in this module: store each answer once and reuse it.

You need C++ strings, std::vector, loops, and substr. You do not need the palindrome partitioning lesson, which asks a different question: how to cut a whole string into palindromes with the fewest cuts. This lesson only counts and lists.

What counts as a palindrome

A palindrome reads the same forwards and backwards. The word level is one. So is aba, and so is a single letter like a. The string abc is not a palindrome, because reading it backwards gives cba.

A substring is a piece of a string made of neighbouring characters. The string abc has six substrings: a, b, c, ab, bc and abc. Its palindromic substrings are a, b and c, so the answer is 3.

We count substrings by where they are, not by their text. Take aaa. It has three single letters, two pairs and one whole string. The pieces are at positions 0, 1 and 2 for the single letters, positions 0-1 and 1-2 for the pairs, and positions 0-2 for the whole string. That is 6 palindromic substrings, even though some of them have the same text. The lists in this lesson keep repeated text, because each copy is a different piece of the string.

Positions run from 0. In a string of n characters the positions are 0 to n - 1. A substring is named by its first and last position, so the piece s[l..r] means the characters from position l up to and including position r.

The idea: every palindrome has a middle

Look at any palindrome. It has a middle. If its length is odd, the middle is one character. In aba the middle is b. If its length is even, the middle is the gap between two characters. In abba the middle is the gap between the two bs.

The centre of a palindrome is the middle. A string of length n has 2n - 1 possible centres. There are n single-character centres, one for each position, because each one can be the middle of an odd-length palindrome. There are n - 1 gap centres, one for each pair of neighbours, because each gap can be the middle of an even-length palindrome. For abc, that is three character centres and two gap centres, five in all.

Here is the key step. Start at a centre and move outward one character on each side at a time. While the two characters you reach are equal, you have found a palindrome. Count it, and move one step further out. When the two characters differ, or you run off the string, stop. No larger palindrome can have this centre, because a larger one would need the characters that just failed to match.

That is the whole method.

A worked example: racecar

Take racecar. Its characters are at these positions.

Start at the centre at position 3, which is the letter e. The left and right indexes both start at 3, so l = 3 and r = 3.

• The two characters are e and e. They match, so e is a palindrome. Count 1.
• Move out: l = 2, r = 4. The characters are c and c. They match, so cec is a palindrome. Count 2.
• Move out: l = 1, r = 5. The characters are a and a. They match, so aceca is a palindrome. Count 3.
• Move out: l = 0, r = 6. The characters are r and r. They match, so racecar is a palindrome. Count 4.
• Move out: l = -1, r = 7. l is no longer on the string, so stop.

The centre at position 3 gives 4 palindromes. The other centres add more. The total for racecar is 10.

Even-length centres

Even-length palindromes need a centre between two positions. Use the gap between positions 1 and 2 in abba. Start with l = 1 and r = 2, the two characters on either side of the gap.

• The characters are b and b. They match, so bb is a palindrome. Count 1.
• Move out: l = 0, r = 3. The characters are a and a. They match, so abba is a palindrome. Count 2.
• Move out: l = -1, r = 4. Stop.

So the gap centre gives 2 palindromes.

Turning centres into indexes in code

A single number c can name every centre in a loop. The rule is simple. If c is even, the centre is a character at position c / 2, and the left and right indexes both start there. If c is odd, the centre is the gap after position c / 2, so the left index is c / 2 and the right index is one more.

Count c from 0 to 2n - 2. That gives 2n - 1 values. Check with abc, where n is 3. The values of c are 0 to 4, which is five centres.

The code

This function counts the palindromes and, if it is given a vector, also stores each one.

#include <iostream>
#include <string>
#include <vector>
 
// Expand around each centre. There are 2n - 1 centres: n single characters
// and n - 1 gaps between neighbours.
long long expandCount(const std::string& s, std::vector<std::string>* out) {
    const int n = static_cast<int>(s.size());
    long long count = 0;
    for (int c = 0; c < 2 * n - 1; ++c) {
        int l = c / 2;
        int r = l + (c % 2);
        while (l >= 0 && r < n && s[l] == s[r]) {
            ++count;
            if (out) out->push_back(s.substr(l, r - l + 1));
            --l;
            ++r;
        }
    }
    return count;
}

The indexes are int and not std::size_t. The reason is explained in the mistakes section, because it is the most common bug in this method. The loop condition checks l >= 0 and r < n before it reads s[l] and s[r]. The order matters. If the characters were read first, the first check that fails would already have read outside the string.

The pointer out can be nullptr. That lets the same function count without building a list, which saves memory when the strings are large.

Running it

The counts below come from expandCount, tableCount and the odd-only version in the mistakes section, run on five strings. The same-list column compares both lists after sorting them.

abc: expand=3 table=3 same list=yes odd-only=3
aaa: expand=6 table=6 same list=yes odd-only=4
abba: expand=6 table=6 same list=yes odd-only=4
racecar: expand=10 table=10 same list=yes odd-only=10
abacdgfdcaba: expand=14 table=14 same list=yes odd-only=14

The expand and table columns are the counts from the two correct methods. The same list column says whether they found the same palindromes. The odd-only column is the count from the wrong version, and it is included to show what goes wrong.

Here is the list of palindromes for abba, in the order the expansion finds them:

expand order for abba: a b bb abba b a

The order follows the centres, and the loop visits each character and each gap in turn. c = 0 is the character at position 0, which finds a. c = 1 is the gap between positions 0 and 1, which finds nothing. c = 2 is the character at position 1, which finds b. c = 3 is the gap between positions 1 and 2, which finds bb and then abba. c = 4 is the character at position 2, which finds b. c = 5 is the character at position 3, which finds a. That gives a, b, bb, abba, b, a. The list is not sorted. Sort it if you need an order.

The table method

The table method takes another route. It asks, for every pair of positions i and j, whether s[i..j] is a palindrome. The answer for a long piece depends on the answer for the piece one character shorter on each side. So the table fills in order of length, shortest first.

Define isPal[i][j] as true when s[i..j] is a palindrome. Two rules fill it.

• A single character is always a palindrome. So isPal[i][i] is true.
• For a longer piece, s[i..j] is a palindrome when the two end characters match, s[i] == s[j], and the piece inside them, s[i+1..j-1], is also a palindrome.

The piece inside is shorter, so its answer is already in the table when you need it. A piece of length 2 has nothing inside. Its two characters only need to match. That is why the code checks len <= 2 before it reads the inside cell.

Here is the code.

// Table: isPal[i][j] is true when s[i..j] is a palindrome. Fill by length.
long long tableCount(const std::string& s, std::vector<std::string>* out) {
    const std::size_t n = s.size();
    std::vector<std::vector<char>> isPal(n, std::vector<char>(n, 0));
    long long count = 0;
    for (std::size_t len = 1; len <= n; ++len) {
        for (std::size_t i = 0; i + len <= n; ++i) {
            const std::size_t j = i + len - 1;
            const bool ok = s[i] == s[j] && (len <= 2 || isPal[i + 1][j - 1]);
            isPal[i][j] = ok;
            if (ok) {
                ++count;
                if (out) out->push_back(s.substr(i, len));
            }
        }
    }
    return count;
}

The len <= 2 check does two jobs. When len is 1, the inside would be isPal[i + 1][i - 1], which points outside the table, so the check must come before that read. The || in C++ stops evaluating its right side when the left side is true, so when len is 1 or 2 the inside cell is never read.

Take abba and fill the table by hand to see the order. Length 1 gives four true cells on the diagonal. Length 2 checks ab, bb, ba, which gives one true cell, bb. Length 3 checks abb and bba. Both have end characters that differ, so both are false. Length 4 checks abba. The end characters are a and a, and the inside bb is true, so abba is true. The final count is 4 + 1 + 1 = 6, which matches the program.

Comparing the two methods

Both methods give the same counts and the same lists. The program checked 3,000 random strings of length up to 11 letters, made of the letters a, b and c, and found zero differences in the sorted lists. Sorting first is needed because the two methods visit the palindromes in different orders.

They differ in cost.

The expansion method uses almost no memory because it only keeps the current l and r. The table keeps a cell for every pair of positions. With vector<vector<char>>, each cell takes one byte. For a string of 3,000 characters, that is 3,000 times 3,000, which is 9,000,000 cells, or about 9 MB. For a string of 100,000 characters, the same table would need 10,000,000,000 cells, which is about 10 GB, and most computers cannot give a program that much memory.

The expansion method stops early at most centres. For a random string, most centres fail after one or two comparisons. The table, however, fills every cell whatever the input.

Both methods have a worst case of about n squared time. For the expansion method, the worst case is a string where every centre expands as far as it can. The program ran the string of 3,000 a letters through both methods. Both gave 4,501,500, which is 3,000 times 3,001 divided by 2. That is the number of pairs of positions i and j where i is less than or equal to j, because every such piece is a palindrome when all letters are the same.

More examples

A string with a centre in the middle

Take aabaa. The program prints each centre and the palindromes it finds. This is the trace from the program, which runs the same loop with a print statement added.

centre 0 (l=0, r=0): a
centre 1 (l=0, r=1): aa
centre 2 (l=1, r=1): a
centre 3 (l=1, r=2): none
centre 4 (l=2, r=2): b aba aabaa
centre 5 (l=2, r=3): none
centre 6 (l=3, r=3): a
centre 7 (l=3, r=4): aa
centre 8 (l=4, r=4): a
total: 9

Look at centre 4, which is the letter b at position 2. It finds three palindromes, b, aba and aabaa, because each step outward matches. The centre at gap 3 (between positions 1 and 2) finds nothing, because a and b differ. Some centres find nothing at all, and that is normal.

Counting by hand with a mix of lengths

Take bb. Its centres are position 0, the gap between 0 and 1, and position 1. The character centres give b at position 0 and b at position 1. The gap centre gives bb, because the two characters match. The total is 3. Notice that the answer includes bb even though it is a piece of length 2, which is an even-length palindrome found from a gap centre.

Stopping at the ends of the string

Take abc. The centre at position 0 finds a, then tries to move left to position -1, which is off the string, and stops. The loop checks l >= 0 before reading s[l], so it never reads position -1. The same stop happens at the right end. Every centre stops at one of the two ends or at the first mismatch. That is why the loop always finishes.

Common mistakes

Only checking odd-length centres

A common error is to write the loop for odd-length palindromes only, so that each character is a centre and nothing else. That misses every palindrome of even length. Here is that wrong version.

// Wrong on purpose: only odd-length centres.
long long oddOnlyCount(const std::string& s) {
    const int n = static_cast<int>(s.size());
    long long count = 0;
    for (int c = 0; c < n; ++c) {
        int l = c, r = c;
        while (l >= 0 && r < n && s[l] == s[r]) {
            ++count;
            --l;
            ++r;
        }
    }
    return count;
}

Its results show the gap.

abba: expand=6 table=6 same list=yes odd-only=4
aaa: expand=6 table=6 same list=yes odd-only=4

The string abba has six palindromes, but the odd-only version finds four. It misses bb and abba, both of which have a centre in a gap. The string aaa shows the same gap. The fix is the rule that c runs over 2n - 1 centres, with odd c meaning a gap.

Using an unsigned index

std::size_t is an unsigned type. It cannot hold a negative value. If you write the centre loop with std::size_t l, the check l >= 0 is always true, because an unsigned number is never less than zero. Then --l at position 0 wraps around to a very large number, and the next s.at(l) throws an exception. This program is the wrong version. It uses at so that the error shows up as a message and does not silently read memory.

terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::at: __n (which is 18446744073709551615) >= this->size() (which is 3)

The number 18446744073709551615 is the largest 64-bit unsigned value, which is what -1 becomes when treated as unsigned. The message tells you the index and the size, so the bug is easy to find once you see the number. Use int for the centre indexes, as the correct code does.

Reading the characters before the bounds check

If the loop reads s[l] == s[r] before checking l >= 0 and r < n, the first time the expansion reaches the end it reads outside the string. In C++ that is undefined behaviour. The program may print a wrong answer, crash, or seem to work. Always put the bounds checks first in the while condition, and let && skip the comparison when a check fails.

Counting pieces as distinct strings

A count of 6 for aaa means six pieces of the string, not six different words. The distinct palindromes of aaa are a, aa and aaa, which is three. Decide which one the problem asks for before you write the code. If the problem asks for distinct words, put the list into a std::set and count its size, or check each word as you add it.

Filling the table in the wrong order

The table method depends on the inside cell being filled before the outside cell. If the loop fills rows from top to bottom and columns from left to right, a cell may read an inside cell that is still 0. The answer is then wrong, but the program does not complain. Filling by length avoids this, because every inside piece is shorter than the outside piece, and shorter pieces are finished first.

Practice

Exercise 1

Count the palindromic substrings of bb by listing them with their positions, and check your answer against the expansion method.

Show the answer

There are three: the b at position 0, the b at position 1, and the whole string bb from position 0 to 1. The expansion method finds these from the three centres. The character centre at 0 finds b, the gap centre between 0 and 1 finds bb, and the character centre at 1 finds b. So the total is 3.

Exercise 2

Trace the expansion for the centre at position 2 in abcba, and list every palindrome it finds.

Show the answer

Start with l = 2 and r = 2, the letter c. It matches itself, so c is found. Move out to l = 1 and r = 3. The letters are b and b, so bcb is found. Move out to l = 0 and r = 4. The letters are a and a, so abcba is found. Move out to l = -1 and r = 5, and stop. The centre finds three palindromes: c, bcb and abcba.

Exercise 3

Explain why the loop in expandCount runs 2n - 1 times, not n times, for a string of length n.

Show the answer

Each palindrome has a centre. Odd-length palindromes are centred on one of the n characters. Even-length palindromes are centred in one of the n - 1 gaps between neighbouring characters. That gives n + (n - 1), which is 2n - 1 centres. The code encodes this with c / 2 for the character or gap position and c % 2 to tell which one it is. A loop that runs only n times would find odd-length palindromes and miss every even-length one.

Exercise 4

Give the number of palindromic substrings of aaaa, and explain how the expansion method gets that number.

Show the answer

There are 10. Every substring of a string of equal letters is a palindrome, and a string of n characters has n * (n + 1) / 2 substrings, which for n = 4 is 10.

The expansion method gets the same total, centre by centre. The character centres at positions 0, 1, 2 and 3 find 1, 2, 2 and 1 palindromes, which is 6. The gap centres between positions 0 and 1, 1 and 2, and 2 and 3 find 1, 2 and 1 palindromes, which is 4. The sum is 6 + 4 = 10.

Check one centre by hand. The centre at position 1 starts with a and a at position 1, then expands to positions 0 and 2, which are also a, so that is 2 palindromes. It cannot expand to positions -1 and 3, because -1 is off the string.

Exercise 5

A string has 1,000 characters. Roughly how many table cells does the table method fill, and how many does it need memory for?

Show the answer

The table is 1,000 by 1,000, which is 1,000,000 cells. The fill loop only visits the upper triangle, where i is less than or equal to j, which is about half of them, but the table still allocates all 1,000,000 cells. With one byte per cell, that is about 1 MB. The expansion method for the same string uses a few integers and nothing that grows with n.

Summary

• Every palindrome has a centre. A string of length n has 2n - 1 centres: n for odd lengths and n - 1 for even lengths.
• Expanding from a centre finds every palindrome with that centre, and it stops at the first mismatch or at the end of the string.
• The table method gives the same counts and lists, but it needs about n squared memory, against almost none for expansion.
• Use int for expansion indexes and check the bounds before reading a character.
• Decide whether the problem counts pieces by position or distinct words before you write the code.