One-Way Robots in a Corridor

Medium

A corridor one cell wide is written as a string of 'L', 'R' and 'X': 'X' is an empty cell, 'L' is a robot that can only drive left, and 'R' is a robot that can only drive right. In one move, a robot shifts one cell in its direction if that cell is empty. In other words, a piece "XL" may become "LX", and a piece "RX" may become "XR". Given two strings before and after of the same length, return True if before can be turned into after by some sequence of such moves (possibly none), and False otherwise.

Example 1

before="RXXL", after="XRLX" → True

The R robot moves one cell right and the L robot one cell left: RXXL → XRXL → XRLX.

Example 2

before="XLR", after="LXR" → True

L slides left into the free cell and R stays where it is.

Example 3

before="RL", after="LR" → False

Robots cannot pass through each other, so they can never swap places.

Constraints

1 ≤ len(before) ≤ 10⁴
len(before) == len(after)
Both strings consist only of 'L', 'R' and 'X'

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

before="RXXL", after="XRLX"

Expected

True

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