Counting Palindromic Substrings

Enumerate every substring and test whether it reads the same forwards and backwards. For each start index, extend the end index and compare the substring with its reverse. Every palindrome is counted exactly once, because each substring has a unique pair of indices.

def count_palindromes(text):
    total = 0
    for i in range(len(text)):
        for j in range(i, len(text)):
            if text[i:j + 1] == text[i:j + 1][::-1]:
                total += 1
    return total

print(count_palindromes("abc"))
print(count_palindromes("aaa"))

The outputs are 3 and 6. In abc the only palindromes are the three single characters. In aaa the palindromes are three single a characters, two substrings of length two, and one of length three, which is six in total.

The mechanism is a double loop over the n times n plus one over two substrings, and each test is itself linear because it builds a reversed copy and compares character by character. So the naive bound is cubic, and even the more careful version that compares characters in place from both ends towards the centre is quadratic.

The trade-off to name is that this version is fine for short strings and useless for long ones. It is also the easiest to get right, which is why it is worth writing first to make sure you understand the counting before optimising. The count itself has a useful closed form that helps you check your work: a string of n characters all of the same letter has n times n plus one over two palindromic substrings, and any string of n characters has at least n of them, one per character.

Every palindrome has exactly one centre, which is either a character for odd lengths or a gap for even lengths. Visit each centre and expand outwards while the characters match, counting one palindrome for every successful expansion.

def count_palindromes(text):
    total = 0
    for center in range(len(text)):
        for left, right in ((center, center), (center, center + 1)):
            while left >= 0 and right < len(text) and text[left] == text[right]:
                total += 1
                left -= 1
                right += 1
    return total

print(count_palindromes("abc"))
print(count_palindromes("aaa"))

The outputs are 3 and 6, matching the brute force version. For aaa the expansions around the three centres find one palindrome at the first centre, three at the second and two at the third, giving six in total, which is every palindromic substring exactly once.

The mechanism is that a palindrome is identified by its centre and its radius, and the expansion loop enumerates those pairs directly rather than enumerating index pairs and testing them. The number of comparisons is the sum of all radii, which is quadratic only when the string is itself a palindrome or close to it.

The trade-off to name is that the worst case is still quadratic, but the constant is far smaller because no substrings are copied and no reversed copies are built. In practice this version is dramatically faster than the brute force one for anything but very short strings. The real reason to care about the worst case is that adversarial input, such as a string of one repeated character, triggers it exactly, so a service that accepts user input and counts palindromes needs a linear-time algorithm to be safe.

Manacher's algorithm transforms the string so that odd and even palindromes can be handled identically, then keeps a radius array together with the rightmost palindrome found so far. When the scan reaches a position inside that known palindrome, the radius there is copied from the mirrored position on the other side of the centre, which avoids redoing work.

def manacher(text):
    t = "^#" + "#".join(text) + "#$"
    radius = [0] * len(t)
    centre = right = 0
    for i in range(1, len(t) - 1):
        if i < right:
            mirror = 2 * centre - i
            radius[i] = min(right - i, radius[mirror])
        while t[i + 1 + radius[i]] == t[i - 1 - radius[i]]:
            radius[i] += 1
        if i + radius[i] > right:
            centre = i
            right = i + radius[i]
    return radius


def count_palindromes(text):
    radius = manacher(text)
    return sum((r + 1) // 2 for r in radius[1:-1])

print(count_palindromes("abc"))
print(count_palindromes("aaa"))

The outputs are 3 and 6 again, which is the sanity check that matters here. The transformed string inserts a separator between every pair of characters and adds sentinels at each end, so an odd palindrome and an even palindrome are both centred on a single position, and the radius at that position counts the characters matched on one side.

The mechanism is the mirror trick. The variable right holds the right edge of the widest palindrome seen so far. Any position inside it has a mirrored counterpart, and palindromes are symmetric, so the radius can be copied rather than recomputed. Only the part that extends beyond the known boundary is expanded by hand, and each character is crossed by the expanding boundary only a constant number of times. That is why the whole thing is linear rather than quadratic.

The trade-off to name is complexity of the code. The algorithm is significantly harder to derive and to debug than expansion around the centre, and the radius-to-count conversion is easy to get wrong by one. In an interview you would rarely be expected to produce this from scratch, but explaining that you know it exists, and that you would use expansion around the centre unless the input size demanded better, is a strong answer. Manacher is also the right building block when you need to answer many palindrome queries about the same string.