Move Pieces to Obtain a String

Move Pieces to Obtain a String

What is this problem about?

The Move Pieces to Obtain a String problem gives you two strings of equal length containing 'L', 'R', and ''. 'L' can move left over '', 'R' can move right over '_', but neither can pass through each other. Determine if string start can be transformed into string end through valid moves. This Move Pieces to Obtain a String coding problem uses a two-pointer approach with movement constraints.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it requires recognizing that the relative order of 'L' and 'R' characters must be preserved, and movement is one-directional per character type. The two pointers and string interview pattern is central, and the problem rewards candidates who can decompose the constraints clearly.

Algorithmic pattern used

Two-pointer constraint check. Use two pointers, one on each string, advancing past '' characters. For each non-'' character pair encountered: if the characters differ in type, return false. If both are 'R', the start pointer must be ≤ end pointer (R can only move right). If both are 'L', the start pointer must be ≥ end pointer (L can only move left). After the loop, both pointers must reach the end simultaneously.

Example explanation

start = "L__R__R", end = "L______RR".

• Skip blanks. Both first non-blank: 'L' at index 1 (start), 'L' at index 0 (end). Type matches (L). start_idx=1 ≥ end_idx=0 ✓ (L moves left, so start was to the right).
• Next: 'R' at index 4, 'R' at index 7. start_idx=4 ≤ end_idx=7 ✓ (R moves right).
• Next: 'R' at index 7, 'R' at index 8. 7 ≤ 8 ✓.
• All checks pass → true.

Common mistakes candidates make

• Checking only character type equality without verifying movement direction constraints.
• Not skipping blank '_' characters correctly.
• Terminating the loop when one pointer finishes but the other hasn't.
• Allowing L to move right or R to move left.

Interview preparation tip

String transformation problems with movement constraints always require encoding the constraints as pointer comparison conditions. The two-pointer technique works here because the relative order of non-blank characters is invariant. Practice problems where characters can move with restrictions — they often reduce to two-pointer checks where you verify that each matched pair satisfies its directional constraint. Drawing the positions on a number line clarifies which direction each character type can move.