One-Way Sliding Tokens

Medium

A narrow track of cells holds two kinds of tokens. A layout is written as a string: L is a token that can only slide left, R is a token that can only slide right, and _ is an empty cell. In one move, any token shifts one cell in its own direction, but only if that neighboring cell is empty. Tokens cannot jump over each other or leave the track. You get two layouts of equal length, current and goal. Return True if goal can be reached from current in any number of moves (zero included), and False otherwise.

Example 1

current="R__L_", goal="_R_L_" → True

Shift the R token one cell to the right; the L token stays put.

Example 2

current="_RL__", goal="__RL_" → False

To reach its spot the L token would have to move right, which it cannot do.

Example 3

current="L__R", goal="_LR_" → False

Both tokens would have to move against their only allowed direction.

Constraints

1 ≤ len(current) = len(goal) ≤ 10⁵
Both strings contain only the characters L, R and _

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Two Pointers String

Similar problems

Longest Mirror Fragment Medium Words in Reverse Order Medium Exactly One Edit Apart Medium Which Release Is Newer Medium Reverse the Word Order in Place Medium

Input

current="R__L_", goal="_R_L_"

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.