Count Palindromic Substrings

MediumStrings#expand-around-center#palindrome~25m

Problem

Given a string s, count its substrings that read the same forwards and backwards. Substrings at different positions count separately even when they spell the same text, and every single character counts as one. Aim for O(n²) time and O(1) extra space.

Examples

Input:  s = "level"
Output: 7
Why:    five single letters, plus "eve" and "level"

Input:  s = "xyz"
Output: 3
Why:    only the single letters

Input:  s = ""
Output: 0
Why:    edge case, an empty string has no substrings to count

Hints

0 / 3

Solution

Each palindrome is fixed by its centre and its length, and growing outward from a centre finds every palindrome around it in order of length, until the first mismatch rules out anything longer. The loop index c covers all 2n - 1 centres: c // 2 and (c + 1) // 2 name the same letter when c is even and two neighbouring letters when c is odd. Each step outward counts exactly one palindrome, so the work is the answer plus one failed check per centre. Time is O(n²) in the worst case, a string of one repeated letter, and space is O(1).

def count_palindromes(s):
    total = 0
    for c in range(2 * len(s) - 1):          # n letters and n - 1 gaps
        lo, hi = c // 2, (c + 1) // 2
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            total += 1                       # one more palindrome around this centre
            lo -= 1
            hi += 1
    return total

print(count_palindromes("level"))   # -> 7
print(count_palindromes("xyz"))     # -> 3
print(count_palindromes(""))        # -> 0

Python · runs in your browser

Stuck on the idea rather than the code? Longest Palindromic Substring covers it.