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 '_'.In #2337 Move Pieces to Obtain a String, you are given two strings containing the characters 'L', 'R', and '_'. The goal is to determine whether the start configuration can transform into the target configuration under specific movement rules: 'L' pieces can only move left, while 'R' pieces can only move right.
A common strategy is to use the two pointers technique. Traverse both strings while skipping the '_' characters and compare the positions of meaningful pieces. First ensure the sequence of 'L' and 'R' is identical in both strings. Then verify movement constraints: an 'L' piece must never move to the right, and an 'R' piece must never move to the left. These positional checks allow you to determine if the transformation is valid.
This approach runs in O(n) time since each string is scanned once, and it uses O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers with Skip Underscores | O(n) | O(1) |
codestorywithMIK
Use these hints if you're stuck. Try solving on your own first.
After some sequence of moves, can the order of the pieces change?
Try to match each piece in s with a piece in e.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like this are common in coding interviews at major tech companies. It tests string processing, pointer techniques, and reasoning about constraints, which are common interview patterns.
No complex data structure is required for this problem. A simple two pointer traversal over the strings is enough to check the sequence and positional constraints of the pieces efficiently.
The optimal approach uses the two pointers technique to scan both strings while skipping underscore characters. By comparing the order and positions of 'L' and 'R', you can validate movement constraints. This method runs in linear time and constant space.
Pieces cannot cross each other because 'L' can only move left and 'R' can only move right. Therefore, the relative order of non-underscore characters must remain identical in both strings for a valid transformation.