The leaded strip

A glazier keeps offcuts of leaded strip: panes of coloured glass soldered in a line. A run that reads the same from either end can be cut out and bent into a border for a round window.

The problem

A strip is recorded as a string, one lowercase letter per pane, in order along the lead. A mirror run is a stretch of consecutive panes that reads the same from either end: gbrbg is one, and so is agga, and so is any single pane.

The glazier wants the longest mirror run, and wants the panes back rather than their positions — the cut is made straight from the answer. Panes must be consecutive: the lead between them is not being unsoldered. If two runs tie for longest, return the one nearer the left end, which is still clamped to the bench.

Input. strip — a non-empty string of lowercase letters.

Output. The longest mirror run, as a string.

Example.

strip = "gbrbgy"   ->  "gbrbg"

Green, blue, red, blue, green. The trailing yellow pane is simply not part of the run.

A second example, where the run has no middle pane:

strip = "yaggagb"   ->  "agga"

The mirror sits between the two greens, not on a pane. A search that only ever grows a run out from one central pane finds gg here and misses agga.

A third, where everything ties:

strip = "rw"   ->  "r"

Constraints.

• 1 <= len(strip) <= 1000
• letters a–z only
• a single pane is a valid answer, so an answer always exists

Hints

Approach

Brute force

Take every start and every end, check the stretch between them pane by pane. That is n(n+1)/2 stretches, each costing up to n comparisons: roughly 1.7 × 10⁸ comparisons at n = 1000, most of them re-reading panes an earlier check already read.

The insight

Every mirror run grows outward from its own centre, and there are only 2n - 1 centres, so expanding from each finds every run without repeating a comparison.

The precondition is the nesting property: shave a pane off each end of a mirror run and you still have one. The runs sharing a centre are therefore a chain, each containing the one before, so expanding outward walks that chain and the first mismatch ends it — nothing wider can match. Two kinds of centre exist, since an odd-length run is centred on a pane and an even-length one on the seam between two. Miss the seams and agga is invisible.

Algorithm

1. Track the best run seen so far, starting with the first pane.
2. For each index c, expand twice: once from the pair (c, c), once from (c, c + 1).
3. While both ends are inside the strip and their panes match, step outward.
4. When the expansion stops, the stretch strictly inside the last step is a mirror run; keep it if it is longer than the best.
5. Return the best run.

Complexity

Time O(n²) — 2n - 1 centres, each expanding at most n/2 steps. Space O(1) beyond the answer itself.

Solution

"""The leaded strip — longest mirror run, by expanding around every centre."""


def grow(strip, left, right):
    """Widest matching stretch around this centre, as (start, length)."""
    while left >= 0 and right < len(strip) and strip[left] == strip[right]:
        left -= 1
        right += 1
    # the loop overshoots by one on each side, so the run is strip[left + 1:right]
    return left + 1, right - left - 1


def solve(strip):
    best_start, best_len = 0, 1
    for centre in range(len(strip)):
        # invariant: best_* names the longest run centred left of this point,
        # earliest kept because a tie never replaces it
        for left, right in ((centre, centre), (centre, centre + 1)):
            start, length = grow(strip, left, right)
            if length > best_len:
                best_start, best_len = start, length
    return strip[best_start:best_start + best_len]

TESTS = [
    (("gbrbgy",), "gbrbg"),
    (("yaggagb",), "agga"),
    (("rw",), "r"),
    (("a",), "a"),
    (("qqqq",), "qqqq"),
    (("abcde",), "a"),
    (("bgggb",), "bgggb"),
]

Pitfalls

• Expanding from single panes only returns gg for yaggagb. Even-length runs are centred on a seam and need their own expansion.
• Off-by-one after the loop — the loop exits with the pointers one step too far apart, so the run is strip[left + 1:right], not strip[left:right + 1].
• Using >= when comparing lengths replaces an earlier run with a later one of the same size and breaks the tie the wrong way, returning w for rw.
• Returning the length or the index when the glazier asked for the glass: the answer is the substring.

Variants

• Mirrored fills — the same expansion, counting every run it finds instead of keeping the longest.
• The sundial motto — checks one fixed stretch for symmetry rather than searching for the best one.