Longest palindromic substring

The longest palindromic substring is the longest unbroken stretch of a string that reads the same backwards, such as TAGGAT inside TTAGGATC. Every palindrome is centred on a letter, when its length is odd, or on the gap between two letters, when it is even, so a string of n letters has 2n − 1 centres. Widening a window from each centre while its two ends match finds the answer in O(n²) time and O(1) extra memory, against O(n³) for checking every substring. That is fast enough for about 10⁴ letters, and the same expansions count every palindromic substring. Manacher’s algorithm reuses what earlier centres proved and runs in O(n) time.

The problem

Four examples:

1. "ACGTGCAT" gives (0, 7): ACGTGCA, of odd length, centred on the T at position 3.
2. "TTAGGATC" gives (1, 6): TAGGAT, of even length, centred between the two Gs.
3. "AGACTCT" gives (0, 3): AGA, CTC and TCT all have length 3, and AGA starts first.
4. "ACGT" gives (0, 1): no letter repeats, so every palindrome is a single letter, and the first one wins.

The brute force: check every substring

Check every substring from both ends and keep the longest palindrome. A strand of n letters has n(n + 1)/2 substrings and each check makes up to n/2 comparisons, so the method is O(n³). One letter repeated is its worst case, because then every check succeeds and runs to the middle. The run counts the comparisons:

# Every substring of a strand, checked from both ends, with the character comparisons counted.

def is_palindrome(s, i, j, counter):
    """Whether s[i..j] reads the same backwards; adds each comparison it makes to counter[0]."""
    while i < j:
        counter[0] += 1
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True


def longest_by_brute_force(s):
    """(start, length) of the leftmost longest palindromic substring, and the comparisons made."""
    counter = [0]
    best = (0, min(len(s), 1))
    for i in range(len(s)):
        for j in range(i, len(s)):
            if is_palindrome(s, i, j, counter) and j - i + 1 > best[1]:
                best = (i, j - i + 1)
    return best, counter[0]


for strand in ["ACGTGCAT", "TTAGGATC", "AGACTCT", "ACGT"]:
    (start, length), work = longest_by_brute_force(strand)
    print(f"{strand:9} start {start}, length {length}: {strand[start:start + length]:7} {work} comparisons")

# One repeated letter is the worst case: every check succeeds and runs to the middle.
print()
for n in (50, 100, 200):
    _, work = longest_by_brute_force("A" * n)
    print(f"{n} copies of A: {work:,} comparisons")

ACGTGCAT  start 0, length 7: ACGTGCA 32 comparisons
TTAGGATC  start 1, length 6: TAGGAT  32 comparisons
AGACTCT   start 0, length 3: AGA     21 comparisons
ACGT      start 0, length 1: A       6 comparisons

50 copies of A: 10,725 comparisons
100 copies of A: 84,575 comparisons
200 copies of A: 671,650 comparisons

Doubling n multiplies the work by about 8, as a cubic cost does: 84,575 comparisons for 100 letters and 671,650 for 200. The same count for 10⁴ letters is 83,345,832,500, and at the rate the constraints lesson gives for C++, about 10⁸ simple steps a second, that is about 14 minutes.

The key idea: expand around every centre

Instead of guessing both ends of a palindrome, fix its centre. Start with the single letter, for an odd centre, or the two letters beside a gap, for an even one, and widen the window one letter on each side while the two new end letters match. The first mismatch ends that centre: every longer window around the same centre contains the two mismatched letters at mirrored positions, so none of them can be a palindrome. Each centre therefore finds the longest palindrome around it, and the longest of those 2n − 1 answers is the result.

The cost depends on how far the windows grow. On one repeated letter they grow to the ends of the strand, and 10⁴ letters cost 50,005,000 comparisons, which C++ makes in about half a second. On a random strand of A, C, G and T, a window grows past the next letter only one time in four, so the work is close to linear. The memory is two indices.

Two more uses come from the same loop. Counting every palindromic substring takes the same expansions: each step that matches adds exactly one palindrome, centred where it was found. Manacher’s algorithm finds the same palindromes in O(n) time by starting each centre from what a mirror position already proved.

A dry run on TTAGGATC

The centres run from left to right, and the best span changes only when a strictly longer palindrome appears, so the first of equally long palindromes is kept.

The answer is (1, 6). Only one of the 15 centres compared more than one pair of letters.

Exercise

longest_palindrome_span("ACGTGCAT")  # (0, 7): ACGTGCA
longest_palindrome_span("TTAGGATC")  # (1, 6): TAGGAT
longest_palindrome_span("AGACTCT")   # (0, 3): AGA, the first of three of length 3

def longest_palindrome_span(s):
    """(start, length) of the leftmost longest palindromic substring of s; (0, 0) for ""."""
    # Replace this line with your code.
    return (0, 0)

import random

from span import longest_palindrome_span


def every_substring(s):
    best = (0, min(len(s), 1))
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            if s[i:j] == s[i:j][::-1] and j - i > best[1]:
                best = (i, j - i)
    return best


def test_examples():
    """the three examples of the prompt"""
    assert longest_palindrome_span("ACGTGCAT") == (0, 7)
    assert longest_palindrome_span("TTAGGATC") == (1, 6)
    assert longest_palindrome_span("AGACTCT") == (0, 3)


def test_short_strings():
    """an empty string, one letter, two letters"""
    assert longest_palindrome_span("") == (0, 0)
    assert longest_palindrome_span("G") == (0, 1)
    assert longest_palindrome_span("GG") == (0, 2)
    assert longest_palindrome_span("GC") == (0, 1)


def test_no_letter_repeats_next_to_itself():
    """no palindrome longer than one letter: the first letter"""
    assert longest_palindrome_span("ACGT") == (0, 1)


def test_whole_strand_and_last_letters():
    """the palindrome may be the whole strand, or reach its last letter"""
    assert longest_palindrome_span("ACCA") == (0, 4)
    assert longest_palindrome_span("GTACCA") == (2, 4)


def test_random_strands_against_every_substring():
    """1,500 random strands, checked against a search of every substring"""
    rng = random.Random(29)
    for _ in range(1500):
        s = "".join(rng.choice("ACGT"[: rng.randint(1, 4)]) for _ in range(rng.randint(0, 14)))
        assert longest_palindrome_span(s) == every_substring(s), f"longest_palindrome_span({s!r})"


def test_three_thousand_letters():
    """n = 3,000: fast enough only without checking every substring"""
    rng = random.Random(41)
    s = "".join(rng.choice("ACGT") for _ in range(3000))
    s = s[:1200] + "GATTACAACATTAG" + s[1214:]
    start, length = longest_palindrome_span(s)
    assert length >= 14
    assert s[start:start + length] == s[start:start + length][::-1]

Centre expansion proved, in five languages, and counted Pro: opens with a Pro, Premium or Ultimate pass

Manacher's algorithm: linear time, with counted comparisons Pro: opens with a Pro, Premium or Ultimate pass

Four bugs reproduced, the variants and a practice set Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• A string of n letters has 2n − 1 centres: n letters for odd palindromes and n − 1 gaps for even ones.
• Widening a window from each centre until its ends differ finds the longest palindrome in O(n²) time and O(1) extra memory; checking every substring costs O(n³).
• The first mismatch ends a centre, because every longer window around it contains the mismatched pair.
• Keep the best span on a strictly greater length to return the palindrome that starts first.