The bead strand mirror

A bead workshop restrings an old strand into a display piece, and the piece has to read the same colour sequence whichever end you start from. Beads may come off; nothing may move.

The problem

The strand is written down as one letter per bead, in thread order — g green, y yellow, b blue, r red. The only allowed operation is to take a bead off the thread; the beads on either side of it close up.

Everything that stays keeps its position relative to everything else: nothing is swapped, nothing is added, and the kept beads need not sit next to each other on the original thread.

Report the largest number of beads that can stay.

Input. strand — a string of lowercase colour letters, in thread order.

Output. The most beads that can remain while the strand reads the same from either end.

Example.

strand = "gybbgyg"  ->  6

Take off the fifth bead, the green between the second blue and the yellow. What is left is g y b b y g, the same from either end. All seven cannot stay, so six is the most on offer.

Example, one strand already mirrored and one with nothing to work with:

strand = "rgbybgr"  ->  7
strand = "rbgy"     ->  1

The first already reads the same from either end, so nothing comes off. In the second every bead is a different colour, so no two can face each other across the middle.

Constraints.

• 0 <= len(strand) <= 1000
• lowercase letters only, one letter per colour
• an empty strand answers 0

Hints

Approach

Brute force

Try every subset of beads and check each one for the mirror property: 2^n subsets, each costing a scan. At twenty beads that is a million checks; at a thousand the number has three hundred digits.

The insight

When the two end beads of a stretch match, keeping both is never wrong, so the only real branching is when they differ.

Take any mirrored selection strictly inside a stretch whose ends match. Wrapping it in those two end beads keeps it mirrored and adds two, so some best answer uses them — there is nothing to decide. When the ends differ they cannot both be the outermost pair of the result, so one of them is gone and the answer is the better of the two stretches you get by dropping each. Both branches are shorter, so stretches settle in order of length.

Algorithm

1. Let keep[i][j] be the most beads that can stay in the stretch from i to j inclusive.
2. A single bead is its own mirror: keep[i][i] = 1.
3. Run i from the last bead down to the first, and j up from i + 1, so both shorter stretches are already filled.
4. Ends the same colour: keep[i][j] = keep[i + 1][j - 1] + 2.
5. Ends different: keep[i][j] = max(keep[i + 1][j], keep[i][j - 1]).
6. Return keep[0][n - 1], and 0 for an empty strand.

Complexity

Time O(n²) — one constant-time cell per stretch, about half a million cells at a thousand beads. Space O(n²) for the table, or two rows of length n when memory is tight, since row i reads only row i + 1.

Solution

"""The bead strand mirror — the longest kept run, one interval at a time."""


def solve(strand):
    """Most beads that can stay so the strand reads the same from either end."""
    n = len(strand)
    if n == 0:
        return 0

    # invariant: keep[i][j] = the largest mirrored subsequence inside the
    # beads strand[i..j]. Intervals are filled shortest first, which is why i
    # counts down: keep[i] reads keep[i + 1], already complete.
    keep = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        keep[i][i] = 1                            # one bead is its own mirror
        for j in range(i + 1, n):
            if strand[i] == strand[j]:
                keep[i][j] = keep[i + 1][j - 1] + 2
            else:
                keep[i][j] = max(keep[i + 1][j], keep[i][j - 1])
    return keep[0][n - 1]

TESTS = [
    (("gybbgyg",), 6),
    (("rgbybgr",), 7),
    (("rbgy",), 1),
    (("bggyrbgyggb",), 9),
    (("",), 0),
    (("b",), 1),
    (("yyyy",), 4),
]

Pitfalls

• Filling i upwards. The recurrence reads row i + 1, which a forward loop has not written yet, so it reads zeros. On "gybbgyg" that reports 2 instead of 6 — and 2 for almost every strand, which hides the cause.
• Letting the inner stretch of an adjacent pair count as 1. When j = i + 1 the cell keep[i + 1][j - 1] covers no beads at all and must hold 0. Seeding it with 1 makes "yy" report 3 — more beads than the strand has.
• Reading it as the longest mirrored run. Beads come off the middle, so the kept beads need not be adjacent. The longest contiguous mirror in "bggyrbgyggb" is three beads; the answer is 9.

Variants

• Marquee changeover — the same match-or-branch table, over two different sequences and their prefixes rather than one sequence and its stretches.
• The seed tray ladder — a subsequence question where the predecessor is forced rather than chosen, so a single dictionary replaces this whole table.