0621MediumStringDynamic ProgrammingSimulation

Beads Sliding Left

Tracked in this browser only

Trains the technique from

LeetCode 2380Time Needed to Rearrange a Binary String

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 groove holds a row of tiles described by s, read from left to right. The character '1' is a bead and '0' is an empty tile.

Every second, all beads move at the same instant: a bead whose immediate left neighbour is an empty tile slides into that tile, and every other bead stays put. Since the moves are simultaneous, whether a bead slides is decided by the layout at the start of the second, not by what its neighbours do during it.

Return the number of seconds after which no bead has an empty tile immediately to its left. If the groove already looks like that, return 0.

Examples

Example 1

Input: s = "0011"
Output: 3

The groove goes `0011` -> `0101` -> `1010` -> `1100`. After the third second no bead has an empty tile on its left.

Example 2

Input: s = "1010"
Output: 1

The groove goes `1010` -> `1100`, so one second is enough: the bead at position 3 slides into position 2 while the bead at position 0 has no empty tile on its left.

Example 3

Input: s = "1111"
Output: 0

There is no empty tile at all, so no bead can ever slide.

Constraints

1 <= s.length <= 1000
s[i] is either '0' or '1'.

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 seconds_to_remove_occurrences(s: str) -> int:

Java

public int secondsToRemoveOccurrences(String s)

The intended approach

Time O(n) — a single pass over the groove.Space O(1) — two integer counters.

One left-to-right pass carries the number of empty tiles seen so far and the finishing second of the most recent bead. For the bead in hand, the count of empty tiles behind it is one lower bound on when it can be settled, because it crosses at most one tile per second. One second after the previous bead's finishing time is another lower bound, because two beads cannot occupy the same tile and the one in front has to clear the way first. Taking the larger of the two lower bounds for each bead in order gives the final answer, and nothing but two counters is stored.

Pythonentry point: seconds_to_remove_occurrences

def seconds_to_remove_occurrences(s):
    # O(n) time, O(1) space. Read the strip once from the left, carrying the
    # number of empty tiles passed so far. A bead with e empty tiles behind it
    # cannot finish before second e, since it has to cross them one per second,
    # and it also cannot finish in the same second as the bead ahead of it, so
    # it needs at least one second more than that bead took. Keeping the larger
    # of the two lower bounds for each bead in turn gives the answer.
    empties = 0
    answer = 0
    for tile in s:
        if tile == '0':
            empties += 1
        elif empties > 0:
            answer = max(answer + 1, empties)
    return answer

The obvious version

Simulate second by second. Within one second, scan the groove left to right and swap every empty tile that is immediately followed by a bead, resuming the scan past each swap so a bead cannot move twice in the same second. Count how many seconds pass before a second changes nothing.

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_seconds_to_remove_occurrences(s):
    strip = s
    seconds = 0
    while '01' in strip:
        strip = strip.replace('01', '10')
        seconds += 1
    return seconds

How this problem was checked

Reference solution executed against 19 test cases — 19 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