Watch 10 video solutions for Move Pieces to Obtain a String, a medium level problem involving Two Pointers, String. This walkthrough by codestorywithMIK has 10,150 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where:
'L' and 'R' represent pieces, where a piece 'L' can move to the left only if there is a blank space directly to its left, and a piece 'R' can move to the right only if there is a blank space directly to its right.'_' represents a blank space that can be occupied by any of the 'L' or 'R' pieces.Return true if it is possible to obtain the string target by moving the pieces of the string start any number of times. Otherwise, return false.
Example 1:
Input: start = "_L__R__R_", target = "L______RR" Output: true Explanation: We can obtain the string target from start by doing the following moves: - Move the first piece one step to the left, start becomes equal to "L___R__R_". - Move the last piece one step to the right, start becomes equal to "L___R___R". - Move the second piece three steps to the right, start becomes equal to "L______RR". Since it is possible to get the string target from start, we return true.
Example 2:
Input: start = "R_L_", target = "__LR" Output: false Explanation: The 'R' piece in the string start can move one step to the right to obtain "_RL_". After that, no pieces can move anymore, so it is impossible to obtain the string target from start.
Example 3:
Input: start = "_R", target = "R_" Output: false Explanation: The piece in the string start can move only to the right, so it is impossible to obtain the string target from start.
Constraints:
n == start.length == target.length1 <= n <= 105start and target consist of the characters 'L', 'R', and '_'.Problem Overview: You are given two strings start and target containing characters L, R, and _ (blank). Pieces can move only in specific directions: L moves left and R moves right by swapping with blanks. The task is to determine whether the start configuration can transform into target under these movement constraints.
Approach 1: Simulate Piece Movement (O(n) time, O(1) space)
This method walks through both strings and simulates how pieces could move through blanks. You skip underscore characters and align the next non-blank characters in both strings. If the characters differ, the transformation is impossible. When they match, enforce movement rules: an L piece cannot appear to the right of its original index because it can only move left, and an R piece cannot appear to the left of its original index because it can only move right. This approach effectively models valid moves while scanning once, making it efficient for large inputs.
Approach 2: Check Character Positions after Removing Blanks (O(n) time, O(1) space)
The key insight is that blanks do not affect the relative ordering of pieces. First remove all underscores from both strings and verify that the remaining sequence of L and R characters is identical. If the order differs, the transformation cannot happen. Next iterate through the original strings using two pointers to compare positions of corresponding pieces. Enforce the constraints: L must not move right and R must not move left. Because each pointer only moves forward once, the scan runs in linear time.
Both strategies rely on the same structural insight: the order of non-blank characters never changes. The problem becomes a positional constraint check rather than actual simulation of swaps. This turns what looks like a movement puzzle into a simple linear scan over a string.
Recommended for interviews: The position-check method using two pointers is the expected solution. It clearly demonstrates understanding of the movement constraints and achieves O(n) time with O(1) extra space. Simulation works too, but recognizing that only relative order and directional constraints matter shows stronger problem-solving insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Piece Movement | O(n) | O(1) | Good for understanding the movement rules step by step |
| Check Character Positions after Removing Blanks | O(n) | O(1) | Preferred interview solution; simplest linear validation using two pointers |