Robots on a one-lane rail

Scenario

A parcel hub in your delivery app moves parcels on a one-lane rail. The rail is a row of cells, and each cell is empty or holds one small robot.

An L robot can only move left. An R robot can only move right. A robot moves one empty cell at a time, and robots cannot pass each other.

The planner stores a start layout and a target layout of the rail. You are asked to decide whether the robots can reach the target by moving any number of times.

Your task

Write can_reach(start, target).

start and target are strings of the same length. Each character is L, R or _. An _ is an empty cell.
A move takes one robot into the empty cell next to it: an L robot one cell left, an R robot one cell right. A robot never moves into a cell that holds a robot, and never leaves the rail.
You may make any number of moves, in any order.
Return true if start can become target, and false otherwise.

Examples

Example 1 (traced)#

text2 lines

Input:  start = "_L__R__R_", target = "L______RR"
Output: true

Two read pointers, i on start and j on target, each skip the empty cells and rest on the next robot. The two robots they find are a pair.

i	j	Pair	Check	Result
1	0	L and L	same kind, and an L may end left of its start: 0 ≤ 1	continue
4	7	R and R	same kind, and an R may end right of its start: 7 ≥ 4	continue
7	8	R and R	same kind, and 8 ≥ 7	continue
9	9	none	both rails are out of robots	true

Example 2#

text2 lines

Input:  start = "R_L_", target = "__LR"
Output: false

The start has an R and then an L. The target has an L and then an R. The R robot would have to pass the L robot.

Example 3#

text2 lines

Input:  start = "_R", target = "R_"
Output: false

The only robot is an R, and it would have to move left.

Constraints

1 ≤ start.length ≤ 100,000, and target.length = start.length (cells on the rail)
Every character of start and target is L, R or _

What does n ≤ 10^5 tell you?

Trying every sequence of moves is a search over layouts. A rail with k robots on n cells has up to n choose k layouts, which is astronomical at n = 100,000. There is no way to visit them all. Aim for one pass over each string.

Robots never pass each other, so their order along the rail never changes. That is the fact that turns the search into a comparison.

Scenario

A parcel hub in your delivery app moves parcels on a one-lane rail. The rail is a row of cells, and each cell is empty or holds one small robot.

An L robot can only move left. An R robot can only move right. A robot moves one empty cell at a time, and robots cannot pass each other.

The planner stores a start layout and a target layout of the rail. You are asked to decide whether the robots can reach the target by moving any number of times.

Your task

Write can_reach(start, target).

start and target are strings of the same length. Each character is L, R or _. An _ is an empty cell.
A move takes one robot into the empty cell next to it: an L robot one cell left, an R robot one cell right. A robot never moves into a cell that holds a robot, and never leaves the rail.
You may make any number of moves, in any order.
Return true if start can become target, and false otherwise.

Examples

Example 1 (traced)#

text2 lines

Input:  start = "_L__R__R_", target = "L______RR"
Output: true

Two read pointers, i on start and j on target, each skip the empty cells and rest on the next robot. The two robots they find are a pair.

i	j	Pair	Check	Result
1	0	L and L	same kind, and an L may end left of its start: 0 ≤ 1	continue
4	7	R and R	same kind, and an R may end right of its start: 7 ≥ 4	continue
7	8	R and R	same kind, and 8 ≥ 7	continue
9	9	none	both rails are out of robots	true

Example 2#

text2 lines

Input:  start = "R_L_", target = "__LR"
Output: false

The start has an R and then an L. The target has an L and then an R. The R robot would have to pass the L robot.

Example 3#

text2 lines

Input:  start = "_R", target = "R_"
Output: false

The only robot is an R, and it would have to move left.

Constraints

1 ≤ start.length ≤ 100,000, and target.length = start.length (cells on the rail)
Every character of start and target is L, R or _

What does n ≤ 10^5 tell you?

Robots never pass each other, so their order along the rail never changes. That is the fact that turns the search into a comparison.