Palindromic Substrings

MediumExpand around centreLeetCode 647 ↗World 5-6

0:00 / 0:00

Count every palindrome hiding in a string. Pick each centre, letter or gap, and expand outward while both ends match, one count per step.

▼

The problem

LeetCode 647 (Medium). Given a string s, return how many of its substrings are palindromes (read the same forwards and backwards). Substrings at different positions count separately, even when their letters are the same.

Examples (LeetCode's): "abc" → 3 (a, b, c) and "aaa" → 6 (a, a, a, aa, aa, aaa).

TRY IT ON LEETCODE ▶

The solution

def countSubstrings(s):
    count = 0
    for c in range(2 * len(s) - 1):
        l, r = c // 2, (c + 1) // 2
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1
            l -= 1
            r += 1
    return count

Transcript

Palindromic Substrings. Given a string, count how many of its substrings are palindromes, reading the same forwards and backwards. Repeats at different positions count separately.

In A, B, C, only the three single letters count, so the answer is three. A A A has three single A's, two A A's, and A A A itself: six.

The naive way checks every substring. There are about n squared of them, and reversing each one costs up to n more. That's order n cubed.

Flip it around: every palindrome has a centre. Pick one and expand outward while both ends match, counting one palindrome per step. In A A B A A, the centre B gives B, then A B A, then A A B A A, all in one sweep. Centres sit on every letter, and on every gap for even lengths: two n minus one in all.

In code, loop over the centres. Start left and right at the centre. While both are in bounds and the letters match, add one, then step outward.

Try A B B A, centre by centre. The first A counts one. The next gap fails, since A and B differ. The first B counts one. The middle gap matches B B, then A B B A: two more. The second B counts one, the last gap fails, and the final A counts one. Six in all.

Two n minus one centres, each expanding at most n steps, is order n squared time, with constant extra space. A dynamic programming table gives the same count, since a substring is a palindrome when its ends match and its inside is one, but it needs order n squared space.

Pick a centre, expand while the ends match, and count every step. That's Palindromic Substrings.