Mirrored fills

A producer is auditing a drum machine pattern. Any stretch of the bar that plays the same reversed can be flipped in the arrangement without anyone noticing.

The problem

A bar on the machine is a row of steps, each holding one drum: k for kick, s for snare, h for hat. The pattern comes to you as a string, one character per step, in playing order.

A mirrored fill is a stretch of consecutive steps that reads the same forwards and backwards. The producer wants to know how many there are. Every stretch counts separately, even when two of them play the same drums, because they sit at different places in the bar and get flipped at different moments. A single step is a mirrored fill of length one.

Input. pattern — a non-empty string of lowercase letters, one per step.

Output. The number of stretches of consecutive steps that read the same in both directions.

Example.

pattern = "ksk"   ->  4

Three single steps, plus ksk itself. The stretches ks and sk are not mirrored.

A second example, where repeats are counted as separate stretches:

pattern = "hhh"   ->  6

Three single steps, two stretches of hh — steps 0–1 and steps 1–2, which are different stretches even though they play the same — and one hhh. Counting distinct patterns instead would give 2.

pattern = "kshsk"   ->  7

Five single steps, plus shs and the whole bar.

Constraints.

• 1 <= len(pattern) <= 1000
• letters a–z only
• the answer fits comfortably in a 64-bit integer; a bar of 1000 identical steps gives 500500

Hints

Approach

Brute force

Enumerate every start and end and test the stretch between them. That is n(n+1)/2 stretches, up to n comparisons each — about 1.7 × 10⁸ comparisons at n = 1000, and the test for a long stretch re-reads exactly what the test for the stretch inside it already read.

The insight

Each successful step of an outward expansion is one whole mirrored fill, so adding one per successful step counts them all without ever forming a stretch.

The nesting property is what licenses this. A mirrored fill with its outer pair removed is still mirrored, so the fills sharing a centre are a chain: the one-step fill, then the three-step, and so on. Expanding from that centre walks the chain and stops at the first mismatch, because nothing wider can match once an inner pair fails. Every fill has exactly one centre, and the centre is either a step or the seam between two steps, so the 2n - 1 expansions between them count every fill exactly once.

Algorithm

1. Start a total at zero.
2. For each index c, run two expansions: from (c, c) and from (c, c + 1).
3. In an expansion, while both ends are inside the bar and their steps match, add one to the total and move both ends outward.
4. Return the total.

Complexity

Time O(n²) — 2n - 1 centres, each expanding at most n/2 steps; 10⁶ step comparisons at the limit. Space O(1) — a counter and two indices.

Solution

"""Mirrored fills — count palindromic stretches by expanding around every centre."""


def fills_from(pattern, left, right):
    """One fill per successful outward step, since each widening is a whole new stretch."""
    found = 0
    while left >= 0 and right < len(pattern) and pattern[left] == pattern[right]:
        found += 1
        left -= 1
        right += 1
    return found


def solve(pattern):
    total = 0
    for centre in range(len(pattern)):
        # invariant: every fill has exactly one centre — a step, or the seam after it —
        # so these two expansions count each stretch once and only once
        total += fills_from(pattern, centre, centre)
        total += fills_from(pattern, centre, centre + 1)
    return total

TESTS = [
    (("ksk",), 4),
    (("hhh",), 6),
    (("kshsk",), 7),
    (("k",), 1),
    (("ksh",), 3),
    (("khhk",), 6),
    (("h" * 1000,), 500500),
]

Pitfalls

• Counting distinct patterns turns hhh into 2 instead of 6. Two stretches at different positions are two fills, however alike they sound.
• Skipping the even centres loses every fill of even length, so hhh comes back as 4 — the singles and the triple only.
• Adding one per centre instead of per successful step counts one fill for each centre and reports 2n - 1 no matter what the bar contains.
• Forgetting the single steps by starting each expansion one pair out undercounts by exactly n.

Variants

• The leaded strip — the same expansion, keeping the longest run rather than counting all of them.
• The sundial motto — the symmetry test itself, on one stretch, with punctuation and case to work around.