Show problems as
Classic problem #777MediumTwo PointersString

Swap Adjacent in LR String

Real-world version: Sliding Tokens in the Chute
Tracked in this browser only
Read Swap Adjacent in LR String on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A single-file chute holds sliding tokens. A configuration of the chute is written as a string, one character per position: '-' is an empty position, 'L' is a token that can only travel toward the front of the chute (lower positions) and 'R' is a token that can only travel toward the back (higher positions).

One move is either of:

  • pick an 'L' whose immediately preceding position is empty, and slide it one position forward into that empty position;
  • pick an 'R' whose immediately following position is empty, and slide it one position back into that empty position.

A token can never pass through another token, and a token never changes kind.

Given the current configuration chute and a wanted configuration target, both of the same length, return true when some sequence of moves turns chute into target, and false otherwise. Zero moves is allowed.

Examples

Example 1

Input
chute = "-LR-", target = "L--R"
Output
true

Sliding the `L` one position forward gives `L-R-`, then sliding the `R` one position back gives `L--R`. Both moves used an adjacent empty position in the token's own direction.

Example 2

Input
chute = "RL-", target = "-RL"
Output
false

The `R` sits at position 0 with the `L` immediately behind it, so it has no empty position to slide into, and the `L` has no empty position in front of it either. No move is possible at all, so `-RL` is out of reach.

Example 3

Input
chute = "RR-", target = "R--"
Output
false

A move never removes a token, so a configuration with two `R` tokens can never become one with a single `R`.

Constraints

  • 1 <= chute.length <= 10^4
  • chute.length == target.length
  • chute and target each consist only of the characters '-', 'L' and 'R'.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def chute_reachable(chute: str, target: str) -> bool:
Java
public boolean chuteReachable(String chute, String target)

More on the same topics