Bracelet from the belt

Beads pass a workbench on a conveyor. You may take a bead or let it go by, but you can never reach back for one that has passed.

The problem

The belt carries coloured beads, written as a string of lowercase letters — r for red, g for green, b for blue, y for yellow. A bracelet pattern is another string of the same letters, and you can thread it if its beads appear along the belt in that order, with any number of unwanted beads skipped between them.

Given the belt and a catalogue of patterns, return the longest pattern you can thread. If two patterns tie on length, return the one that comes first alphabetically, because that is how the catalogue is filed. If none can be threaded, return the empty string.

Input. belt — a string of bead colours in the order they pass. patterns — a list of candidate pattern strings.

Output. The chosen pattern, or "".

Example.

belt = "rgbyrgby"
patterns = ["rgby", "rry", "gbb", "ryby"]   ->  "rgby"

rgby threads from the first four beads. ryby also threads — red at 0, yellow at 3, blue at 6, yellow at 7 — and is the same length, so the alphabetical tie-break picks rgby. rry fails: there is only one red before any yellow. gbb fails: the belt never shows a second blue after the first.

A second example, where the beads are all present but in the wrong order:

belt = "gbr"
patterns = ["rgb"]                          ->  ""

Every colour rgb needs is on the belt, and it still cannot be threaded: the red passes last.

Constraints.

• 1 <= len(belt) <= 10^4
• 0 <= len(patterns) <= 10^3
• 1 <= len(pattern) <= 10^3
• Belt and patterns use lowercase letters only.

Hints

Approach

Brute force

Enumerate every subsequence of the belt and check each against the catalogue. A belt of length n has 2^n subsequences — for n = 30 that is already a billion, and the belt can be 10^4 beads long.

The insight

Take the first matching bead you see: the greedy match uses the earliest possible bead for each position, so if greedy fails, nothing succeeds.

Suppose some threading exists. Its first bead sits at or after the first belt position of that colour, so swapping in the earliest copy leaves the rest of the threading still ahead of the pointer. Repeating that bead by bead turns any valid threading into the greedy one, which makes a single forward walk a complete test.

Algorithm

1. Keep best = "".
2. For each pattern, set a pattern pointer to 0 and walk the belt once.
3. Whenever the current bead equals the bead the pattern wants, advance the pattern pointer.
4. The pattern threads if its pointer reached the end.
5. Replace best when the pattern is longer, or the same length and alphabetically earlier.
6. Return best.

Complexity

Time O(k * n), for k patterns and a belt of n beads — each test is one forward walk and the pattern pointer never moves backwards. Space O(1) beyond the answer, since only two indices are held.

Solution

"""Bracelet from the belt — a two-pointer subsequence test per candidate pattern."""


def is_orderable(pattern, belt):
    """True when pattern's beads appear along belt in the same order."""
    p = 0
    for bead in belt:
        if p < len(pattern) and bead == pattern[p]:
            p += 1              # invariant: pattern[:p] is matched by the belt so far
    return p == len(pattern)


def solve(belt, patterns):
    best = ""
    for pattern in patterns:
        if not is_orderable(pattern, belt):
            continue
        # Longer wins; on a tie the alphabetically earlier pattern wins.
        if len(pattern) > len(best) or (len(pattern) == len(best) and pattern < best):
            best = pattern
    return best

TESTS = [
    (("rgbyrgby", ["rgby", "rry", "gbb", "ryby"]), "rgby"),
    (("yygbb", ["ygb", "gy", "yb"]), "ygb"),
    (("rrr", ["rb", "bb"]), ""),
    (("gbr", ["rgb"]), ""),
    (("bygbygbyg", []), ""),
    (("b", ["b", "bb"]), "b"),
]

Pitfalls

• Checking that the letters are merely present. Counting colours accepts rgb against the belt gbr and returns a bracelet that cannot be threaded.
• Advancing the belt pointer only on a match. With belt = "yygbb" and pattern ygb, the walk sticks on the second y and never reaches g; the belt pointer has to move on every bead, matched or not.
• Keeping the first pattern of maximal length. On the first example that returns whichever of rgby and ryby the catalogue lists first, so the tie-break has to compare strings, not arrival order.

Variants

• Shared sightings — two sequences again, but order carries no information there, so a set replaces the walk.