1162HardStringDynamic ProgrammingStackBreadth-First SearchMemoization

Clearing the Rail of Beads

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A rail holds beads, given by rail, and a pouch holds spares, given by pouch. Both are written with the letters R, Y, B, G and W, one letter per bead.

One move takes a bead out of the pouch and pushes it in anywhere on the rail, either end included. Then, over and over for as long as it applies, any run of three or more touching beads of one colour is taken off the rail, which may bring fresh runs together.

The rail starts with no run of three or more beads of one colour.

Return the fewest beads that have to leave the pouch to clear the rail completely, or -1 when no number of moves can clear it.

Examples

Example 1

Input: rail = "RRBBRR", pouch = "B"
Output: 1

Pushing the spare between the two middle beads makes three of that colour. Taking those off brings the four outer beads together, and they come off as well, so one bead clears the rail.

Example 2

Input: rail = "WRRW", pouch = "RW"
Output: 2

Push the first spare between the two middle beads to make three, which come off and leave the outer pair touching. The second spare then makes three of those.

Example 3

Input: rail = "RY", pouch = "RY"
Output: -1

Each colour appears once on the rail and once in the pouch, so no colour can ever reach three touching beads.

Constraints

1 <= rail.length <= 16
1 <= pouch.length <= 5
rail and pouch hold only the letters R, Y, B, G and W
the rail starts with no run of three or more beads of one colour

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_min_step(rail: str, pouch: str) -> int:

Java

public int findMinStep(String rail, String pouch)

The intended approach

Time O(states * pouch * rail) with the pouch shrinking every move.Space O(states) for the answers remembered.

The pouch holds at most five beads, so at most five moves are ever made and every move takes one bead out for good. That means the search can never circle back on itself, and what is left of the rail together with what is left of the pouch is the whole state of play. So try every move from a state: for each colour still in the pouch and each of the places a bead could go, build the rail that results, let the removals settle, and solve what is left with the smaller pouch. Take the cheapest of those that ever clears the rail. The settling has to keep going until nothing more comes off, because taking a run away joins its neighbours and can set off another run. Two things keep the search small. States already worked out are remembered, since the same rail and pouch can be arrived at by different orders of moves. And two beads of the same colour in the pouch are interchangeable, so with the pouch in order only the first of each colour is tried at each step.

Pythonentry point: find_min_step

def find_min_step(rail, pouch):
    def settle(text):
        while True:
            n = len(text)
            i = 0
            cut = -1
            stop = -1
            while i < n:
                j = i
                while j < n and text[j] == text[i]:
                    j += 1
                if j - i >= 3:
                    cut = i
                    stop = j
                    break
                i = j
            if cut < 0:
                return text
            text = text[:cut] + text[stop:]

    known = {}

    def solve(board, hand):
        if board == "":
            return 0
        if hand == "":
            return -1
        key = (board, hand)
        if key in known:
            return known[key]
        known[key] = -1
        answer = -1
        for i in range(len(hand)):
            if i > 0 and hand[i] == hand[i - 1]:
                continue
            colour = hand[i]
            rest = hand[:i] + hand[i + 1:]
            for spot in range(len(board) + 1):
                grown = settle(board[:spot] + colour + board[spot:])
                got = solve(grown, rest)
                if got >= 0:
                    if answer < 0 or got + 1 < answer:
                        answer = got + 1
        known[key] = answer
        return answer

    return solve(rail, "".join(sorted(pouch)))

The obvious version

Walk outwards from the starting state a move at a time, breadth first, so the first state reached with an empty rail used the fewest beads. From each state, push every remaining pouch bead into every place and let the removals settle by sweeping the whole rail for runs and rebuilding it until a sweep changes nothing. States already reached are skipped, and a search that runs dry means the rail cannot be cleared.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_min_step(rail, pouch):
    from collections import deque

    def settle(text):
        changed = True
        while changed:
            changed = False
            out = []
            n = len(text)
            i = 0
            while i < n:
                j = i
                while j < n and text[j] == text[i]:
                    j += 1
                if j - i < 3:
                    out.append(text[i:j])
                else:
                    changed = True
                i = j
            text = "".join(out)
        return text

    start = "".join(sorted(pouch))
    seen = set([(rail, start)])
    queue = deque([(rail, start, 0)])
    while queue:
        board, hand, used = queue.popleft()
        if board == "":
            return used
        for i in range(len(hand)):
            colour = hand[i]
            rest = hand[:i] + hand[i + 1:]
            for spot in range(len(board) + 1):
                grown = settle(board[:spot] + colour + board[spot:])
                state = (grown, rest)
                if state not in seen:
                    seen.add(state)
                    queue.append((grown, rest, used + 1))
    return -1

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in