0684MediumTwo PointersString

Shunting Trolleys Along a Siding

Tracked in this browser only

Trains the technique from

LeetCode 2337Move Pieces to Obtain a 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 single-track siding is written as a string, one character per bay:

'<' is a trolley whose brake lets it be pushed only towards the left end;
'>' is a trolley whose brake lets it be pushed only towards the right end;
'.' is an empty bay.

One push moves a single trolley one bay in its allowed direction. A push is legal only when the destination bay lies on the siding and is empty, so a trolley can never be pushed off an end of the siding and can never be pushed onto an occupied bay.

You are given the current layout start and a wanted layout goal, both of the same length. Return true if some sequence of legal pushes turns start into goal, and false otherwise. Zero pushes is a valid sequence.

Examples

Example 1

Input: start = ".<..>", goal = "<...>"
Output: true

One push takes the `'<'` from bay 1 into the empty bay 0, which is its allowed direction. The `'>'` already sits where the goal wants it.

Example 2

Input: start = "<.>", goal = "<>."
Output: false

The goal asks the `'>'` to end up in bay 1, which is to the left of the bay 2 it starts in, and a `'>'` can only be pushed rightwards.

Example 3

Input: start = "<.", goal = "<<"
Output: false

The goal shows two trolleys while the siding holds one, and a push never adds a trolley.

Constraints

1 <= start.length <= 10^5
start.length == goal.length
start and goal contain only the characters '<', '>' and '.'.

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 can_shunt(start: str, goal: str) -> bool:

Java

public boolean canShunt(String start, String goal)

The intended approach

Time O(n) for a siding of n bays: each cursor advances only forwards.Space O(1).

Because a push never lets one trolley get past another, the trolleys keep their order, so walk both sidings with one cursor each, skipping empty bays and lining up the k-th trolley of `start` with the k-th trolley of `goal`. Each lined-up pair must be the same kind of trolley, a `'<'` must not be asked to end up in a higher-numbered bay, and a `'>'` must not be asked to end up in a lower-numbered bay. Both cursors also have to run out of trolleys at the same time.

Pythonentry point: can_shunt

def can_shunt(start, goal):
    n = len(start)
    i = 0
    j = 0
    while True:
        while i < n and start[i] == '.':
            i += 1
        while j < n and goal[j] == '.':
            j += 1
        if i == n or j == n:
            return i == n and j == n      # both sides must run out together
        if start[i] != goal[j]:
            return False
        if start[i] == '<' and i < j:
            return False                  # a left-only trolley cannot end up further right
        if start[i] == '>' and i > j:
            return False                  # a right-only trolley cannot end up further left
        i += 1
        j += 1

The obvious version

Explore reachable layouts directly: from a layout, generate every layout one legal push away, and keep exploring unseen ones until the goal turns up or the search is exhausted. The number of layouts grows exponentially with the siding length, so this is only usable on short sidings.

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_can_shunt(start, goal):
    if len(start) != len(goal):
        return False
    seen = {start}
    frontier = [start]
    while frontier:
        cur = frontier.pop()
        if cur == goal:
            return True
        n = len(cur)
        for i in range(n):
            if cur[i] == '<' and i > 0 and cur[i - 1] == '.':
                nxt = cur[:i - 1] + '<.' + cur[i + 1:]
            elif cur[i] == '>' and i + 1 < n and cur[i + 1] == '.':
                nxt = cur[:i] + '.>' + cur[i + 2:]
            else:
                continue
            if nxt not in seen:
                seen.add(nxt)
                frontier.append(nxt)
    return False

How this problem was checked

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