2337. Move Pieces to Obtain a String - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Definition: We are given two strings start and target of equal length n, each consisting of three possible characters: 'L', 'R', or '_'. Here, 'L' and 'R' represent movable pieces and '_' represents an empty space (blank). We can move these pieces under specific rules:

A piece 'L' can move one step to the left only if the immediate left position is blank ('_').
A piece 'R' can move one step to the right only if the immediate right position is blank.
Pieces cannot jump over each other or move multiple steps in one go (but can move step-by-step repeatedly).
The blank '_' can be occupied by any piece moving into it.

The task is to determine if we can transform the start string into the target string by performing any number of valid moves of the pieces. We should return true if it is possible to reach target from start, otherwise return false.

Key Points:

We cannot add or remove pieces; we can only slide them into blanks. This means start and target must have the same number of 'L' pieces and the same number of 'R' pieces (and consequently the same number of blanks).
'L' pieces can only ever move leftwards (never to the right), and 'R' pieces only move rightwards (never to the left). They also cannot cross each other in the process. This implies the relative order of the pieces (ignoring blanks) in start and target must be the same.

Examples:

Example 1:
- Input: start = "_L__R__R_", target = "L______RR"
- Output: true
- Explanation: We can achieve the target by moving pieces in start as follows:
  - Move the 'L' piece one step to the left (into the blank at its left). Now start becomes "L___R__R_".
  - Move the last 'R' piece one step to the right (into the blank at its right). Now start becomes "L___R___R".
  - Move the remaining 'R' piece (which was originally in the middle of start) three steps to the right, one step at a time, until it occupies its position in target. Now start becomes "L______RR", which matches target.
    All moves are valid, so the transformation is possible.
Example 2:
- Input: start = "R_L_", target = "__LR"
- Output: false
- Explanation: We try to transform start into target:
  - The 'R' at the beginning of start can move one step to the right into the blank, giving "_RL_". After this, no further moves can help achieve target. The target order "__LR" requires the 'L' piece to end up to the left of the 'R' piece, but in start the 'L' is to the right of 'R'. Because the pieces cannot cross each other, we cannot get the order "LR" from "RL". Thus, it's impossible to reach the target.
Example 3:
- Input: start = "_R", target = "R_"
- Output: false
- Explanation: The start string has one 'R' piece at index 1 and a blank at index 0, while target wants the 'R' at index 0. To achieve target, the 'R' would need to move left. However, 'R' pieces are not allowed to move left, only right. Therefore, this transformation is not possible.

These examples illustrate the rules: pieces can't appear out of nowhere or disappear, the sequence of pieces (ignoring blanks) must remain consistent, and each piece can only move in its allowed direction into blanks.

Hints to Guide the Solution

Hint 1: Think about the order of the pieces. After any sequence of moves, can an 'L' that started to the right of an 'R' ever end up to the left of that 'R'? (Remember, pieces cannot jump over or pass through each other.) The relative ordering of 'L' and 'R' pieces in the string cannot change after moves. This means if target has a different order of L's and R's than start (when you remove the blanks), the answer is immediately false.
Hint 2: Try ignoring the blanks ('_') and just line up the pieces in start and target. For example, represent start and target by the sequence of their pieces (e.g., "LRR"). If these sequences differ (different order of L's and R's), the transformation is impossible. If they match, consider how each corresponding piece can move.
Hint 3: Once you know the pieces line up in the same order, focus on each piece's target position relative to its start position. An 'L' piece can only move leftwards, so it can only end up at an index less than or equal to its starting index. Similarly, an 'R' can only move rightwards, so it can only end up at an index greater than or equal to its starting index. In other words:
- If an 'L' is at position i in start and at position j in target, we must have i ≥ j for the move to be possible.
- If an 'R' is at position i in start and at position j in target, we must have i ≤ j for the move to be possible.
Hint 4: Consider using a two-pointer technique to iterate through start and target together, skipping blanks and comparing the positions of corresponding pieces. This can efficiently check the conditions from Hint 3 for all pieces.

Brute Force Approach

A naive approach would be to try simulating all possible moves of the pieces to see if we can reach the target configuration. For instance, we could repeatedly move any 'L' left or any 'R' right into blanks and explore all resulting strings (like a state-space search). This would essentially be a brute-force or backtracking search through all configurations of pieces.

However, this approach is extremely inefficient because the number of possible configurations grows explosively with the string length and number of pieces. In the worst case, with n up to 100,000, there are astronomically many ways to move pieces around. Even for small strings, exploring every sequence of moves is impractical:

Each piece might move multiple times, and moves can be done in different orders.
We would be revisiting many similar states or getting stuck trying redundant moves.

For example, consider a smaller case: start = "R_L", target = "_RL". A brute force might try moving R or L in different orders, but many sequences won't lead to the solution. As n grows, a brute-force search would have to consider an enormous search tree of moves.

Why it's inefficient: For each move, there could be several choices (which piece to move), and moves can repeat many times. The complexity is exponential in the number of moves, which is infeasible for large n. Therefore, we need a more clever strategy that avoids exploring all possibilities explicitly.

Optimized Approach (Two-Pointer Greedy Strategy)

To solve this efficiently, we can use a greedy two-pointer approach that leverages the insights from the hints:

Validate Piece Order and Counts: First, check if start and target even have the same multiset of pieces. Remove all '_' from both strings and compare the resulting sequences. If they differ (meaning the order of 'L' and 'R' pieces is not identical), return false immediately. This ensures both strings contain the same number of 'L's and 'R's and in the same relative order. (If this condition fails, no amount of movement can fix a different order or different counts of pieces.)
Use Two Pointers to Match Pieces: Initialize two pointers, say i for start and j for target, both starting at index 0. We'll scan through both strings simultaneously:
- Advance i until it points to a character in start that is not '_' (i.e., skip over blanks). Do the same for j in target.
- Now, start[i] and target[j] should both point to a piece ('L' or 'R'). If one string runs out of pieces before the other, or the characters at these positions are different (one is 'L' and the other is 'R'), then the transformation is impossible (return false).
- If the characters match (say both are 'L' or both are 'R'), check their indices:
  - If it's 'L' and the index in start (i) is less than the index in target (j), then this 'L' piece in start would have to move right to reach position j, which is not allowed. So, return false in this case.
  - If it's 'R' and the index in start (i) is greater than the index in target (j), then this 'R' piece would have to move left to reach position j, which is not allowed. So, return false in this case.
- If those checks pass, it means this piece can potentially move to its target position. Then we move both pointers i and j one step forward and continue the process.
- Continue until we have checked all pieces in both strings. If we finish without finding any conflicting condition, then return true.

This greedy approach effectively "pairs up" each piece in start with its corresponding piece in target (since we confirmed the sequences match). By checking the relative indices, we ensure that each 'L' and 'R' can actually travel to the needed position without violating movement rules.

Why this works: If all pieces are in the correct relative order and satisfy the index constraints (i.e., every 'L' in start is positioned to the right of or at the same position as its target position, and every 'R' in start is to the left of or at the same position as its target position), then we can always find a sequence of moves to transform the string. Essentially, you can move each 'L' leftwards into its target spot (there will always be blanks available on its left when needed, because no 'R' will block it) and move each 'R' rightwards into its spot (no 'L' will be blocking from the right). The two-pointer check ensures no piece violates these conditions. If a violation exists, no sequence of moves can overcome it.

Let's apply this approach to an example to clarify the process:

Example walkthrough (using the two-pointer logic):
Consider start = "_L__R__R_" and target = "L______RR" (from Example 1).
- Remove '_': both give the sequence "LRR", which matches, so we proceed.
- Set i=0, j=0.
  - start[0] is '_', skip it (increment i until i=1). Now start[1] = 'L'.
  - target[0] is 'L' (no skip needed for j since target[0] is already a piece). Now we compare the pieces: both are 'L'. Check indices: i=1 in start vs j=0 in target. Since i (1) ≥ j (0), this is okay for 'L' (the L in start is to the right of where it needs to go, so it can move left).
  - Move i and j to the next positions (i=2, j=1).
  - start[2] and start[3] are '_', skip to i=4 where start[4] = 'R'.
  - target[1] through target[6] are '_', skip to j=7 where target[7] = 'R'. Now compare: both are 'R'. Check indices: i=4 vs j=7. Here i (4) ≤ j (7), which is okay for 'R' (the R in start is to the left of or at the same position as in target, so it can move right to reach index 7).
  - Move i and j forward (i=5, j=8).
  - Skip blanks in start again: start[5] and start[6] are _, so i becomes 7. start[7] = 'R'.
  - target[8] = 'R'. Compare pieces: both 'R'. Check indices: i=7 vs j=8. i (7) ≤ j (8) is fine for 'R'.
  - Move i and j (i=8, j=9). Now j has reached the length of the string and i will also skip the last underscore and reach the end. We've successfully matched all pieces without a rule violation, so the result is true.
This matches our earlier conclusion that the example is solvable.

Code Implementations

Below are implementations of the above approach in both Python and Java. Each includes a simple test in the main (or equivalent) to demonstrate the function.

Python Implementation

Python3

. . . .

Explanation: The Python code first checks if the sequence of 'L' and 'R' matches between start and target by removing underscores. Then it uses two pointers (i for start, j for target) to find each next piece and verify the movement constraints for 'L' and 'R'. If any check fails, it returns False; otherwise, if it completes the scan successfully, it returns True.

Java Implementation

Java

. . . .

Explanation: The Java code follows the same logic. It first checks if the sequence of pieces (excluding blanks) is identical. Then it uses two indices i and j to traverse start and target. It skips blanks and compares each found piece. If an 'L' in start is found at an index less than its index in target, or an 'R' in start is at a greater index than in target, it returns false. If all pieces satisfy the movement constraints, it returns true. The main method provides a few examples to test the implementation.

Complexity Analysis

Brute Force: The brute force approach of trying all possible moves would be extremely inefficient. In the worst case, the number of possible move sequences grows exponentially with the number of moves, which is infeasible for even moderate string lengths. There is no straightforward formula for the time complexity of the brute force, but it would be practically non-computable for n = 10^5. The state space (all arrangements of pieces in blanks) is huge — for example, if there are k pieces, there are $\binom{n}{k}$ ways to place them in n positions, and exploring each arrangement could take multiple moves. This is why we rule out brute force.
Optimized Two-Pointer Approach: We only traverse the strings a couple of times:
- Removing underscores from both strings to compare sequences takes O(n) time and O(n) space in the worst case.
- The two-pointer scan then goes through each string once, which is O(n) time.
- Overall time complexity is O(n), linear in the length of the strings. This is efficient even for n up to 100,000.
- Space complexity is O(1) extra space (beyond the input strings) if we do the comparison in-place using pointers. If we explicitly create the filtered strings (without underscores), that uses O(n) extra space, but this is still linear. We can avoid that extra space by comparing on the fly with pointers as we did in the code (skipping blanks and matching pieces without storing a new string).

In summary, the optimized solution runs in linear time, which is optimal for this problem, and uses constant additional space (or linear if counting a copy of the string for comparison, but that's acceptable given the input size).

Step-by-Step Walkthrough of the Solution

Let's visually walk through how the solution works with a simple example, detailing each step:

Suppose start = "R_L_" and target = "_RL_". (This is a variant to illustrate the method; it is actually possible to transform start to target in this case.)

Initial strings:
- start: R _ L _
- target: _ R L _
- (Here spaces are added just for clarity to show characters; actual strings have no spaces.)

Remove underscores and compare piece order:
- start without _ is "RL".
- target without _ is "RL".
- They match (both have the sequence "R then L"). So the basic order of pieces is compatible. We can proceed.
Two-pointer iteration (i for start, j for target):
- Initialize i = 0, j = 0.
- At i=0, start[i] = 'R' (not an underscore, so this is our first piece in start).
  At j=0, target[j] = '_' (blank, not a piece). We skip over blanks in target: move j to 1. Now target[1] = 'R'.
  - We have found the next piece in each string: 'R' in start at index 0, and 'R' in target at index 1`. They are the same type of piece ('R').
  - Check movement constraint for this 'R': in start it's at index 0, in target at index 1. Since 0 ≤ 1, it's okay for 'R' (it can move right to index 1).
  - We can imagine actually moving this R one step right in the string: start would become "_RL_" after the move, which now matches the target. Our algorithm doesn't explicitly do the move, but the logic confirms it's possible.
  - Increment both i and j to look for the next pieces (i=1, j=2 now).
- At i=1, start[i] = '_', skip it (i→2). Now start[2] = 'L'.
  At j=2, target[j] = 'L' (found a piece straight away).
  - We have 'L' in start at index 2, and 'L' in target at index 2`.
  - Check constraint for 'L': start index 2 vs target index 2. Since 2 ≥ 2, that's okay (the L doesn't need to move right; in fact, it's exactly where it needs to be in this case).
  - This piece is fine. Increment i and j (i=3, j=3).
- Now both i and j move to 3, and then skip the final underscores and reach the end of the strings. We've matched all pieces with valid moves.
Result: Since all pieces could be matched under the rules, the algorithm would return true for this example. Indeed, as we saw, one valid sequence of moves is: R_L_ -> _RL_ by moving the R one step to the right.

This walkthrough shows how the algorithm methodically checks each piece. It doesn't actually perform the moves on the string in code, but by ensuring the conditions for each move are satisfied, it guarantees that a sequence of moves exists. If any check fails (for example, if we had needed an R to move left or an L to move right), the algorithm would return false, correctly indicating that no valid sequence of moves can achieve the target.

Visualizing moves for one of the earlier examples (Example 1) in terms of the actual board:

Start: _ L _ _ R _ _ R _ (pieces at positions 1, 4, 7)
Target: L _ _ _ _ _ _ R R (pieces should be at positions 0, 7, 8)
We can move the L from index 1 to index 0 (left) because index 0 is blank.
We can move the R from index 7 to index 8 (right) because index 8 is blank.
We can then move the R from index 4 step by step to the right until it reaches index 7 (those positions become blank one by one as the R moves).
At each step, the move is valid (R always moves into a blank on its right, L moved into a blank on its left). The end configuration matches target.

Common Mistakes

Not checking piece order: A frequent mistake is to jump into movement logic without verifying that start and target have the same sequence of L's and R's. If you don't check this, you might incorrectly think you can swap the order of pieces. Always ensure the pieces appear in the same order (just possibly in different positions with blanks in between) before proceeding.
Allowing illegal moves: It's easy to mess up the conditions on indices. Remember that 'L' can never move rightward, and 'R' can never move leftward. A mistake would be flipping these conditions. For example, one might incorrectly allow an 'L' at index 2 in start to go to index 5 in target (moving right), which should be disallowed. Be careful with the inequality signs: for 'L', start_index should be >= target_index; for 'R', start_index should be <= target_index.
Skipping blanks incorrectly: When implementing the two-pointer approach, ensure that you skip over '_' in both strings properly. Forgetting to skip blanks will cause you to compare wrong characters. Similarly, make sure when one pointer reaches the end (past the last character), the other pointer should also be at the end if everything is matched; otherwise, there's a mismatch in piece count.
Considering crossing movements: Some might try to simulate moves and inadvertently allow pieces to cross paths (for example, thinking an 'R' can go around an 'L' by swapping positions). This is not possible under the rules. The logic of the solution inherently prevents crossing because it requires the relative order to remain the same. But if you're thinking in terms of moves, be mindful that pieces can't jump over each other or occupy the same space at the same time.
Edge cases not handled: Make sure to handle cases like an all-blanks string, or strings with one character, or already-equal strings. It's easy to assume certain pieces exist and then run into issues on extreme cases.

Edge Cases to Consider

Already Equal: If start is exactly the same as target, the answer should be true (no moves needed). Our algorithm handles this by the initial sequence check (they'll match and then the pointers will finish without finding issues).
All Blanks: If both strings are all '_' (no pieces at all), it's trivially true because there's nothing to move (they're already the same). The sequence comparison would yield empty strings which match, and the pointer loop would exit immediately.
Unequal Counts: If start and target have different numbers of 'L' or 'R', it should return false immediately. For example, start = "L__", target = "___" (one has an L, the other doesn't) or start = "RR_", target = "R_R" (both have two R's but in one string the order is different). The algorithm's sequence check covers these cases by simple string inequality.
Pieces at Boundaries: Cases where pieces are at the very left or right end:
- An 'L' at index 0 in start cannot move anywhere (it's already at left edge, and it can't go right), so for it to match target, target must also have an 'L' at index 0. If target wanted that L at any other position, it would be impossible.
- An 'R' at the last index n-1 in start similarly cannot move, so if target wants that R elsewhere, it's impossible.
- Likewise, an 'L' that target expects at the far left must already be at or to the right of that position in start (which essentially means it might already be there or further right), and an 'R' expected at the far right of target must already be at or to the left of that position in start.
No Blanks to Move Into: If a piece in start is boxed in by other pieces such that it can't move but in target it needs to, that's a failure case. For example, start = "LR" and target = "RL" is impossible because the L and R would have to swap places, but neither can move through the other or in the wrong direction. Our checks catch this since the order "LR" vs "RL" wouldn't match.
Large Strings Performance: While not a distinct scenario in terms of logic, remember that the solution must handle very long strings efficiently. Our approach does this in linear time. If someone attempted something like repeatedly replacing substrings or using expensive operations inside a loop, it might time out on large inputs.

This problem is essentially about checking if one configuration can transform into another given movement constraints. There are a few similar or related problems that can provide additional practice and deepen understanding:

Swap Adjacent in LR String (LeetCode 777): This is a very closely related problem. Instead of '_', it uses 'X' to denote an empty space, and it asks if you can transform one string into another by swapping adjacent "XL" -> "LX" or "RX" -> "XR". The logic is almost identical to the one we used: you must match the relative order of L and R and check the movement constraints. Solving this problem uses the same two-pointer strategy.
Push Dominoes (LeetCode 838): In this problem, you have a string with characters 'L', 'R', and '.', representing dominoes falling to the left, right, or standing still. While the scenario is different, understanding how forces propagate only in one direction (left or right) has some conceptual similarity to pieces moving in only one direction. It's a different problem (more about final state after pushes), but it could be interesting to see the contrast.
Sliding Puzzle (LeetCode 773): This is a 2D puzzle (the 8-puzzle) where you slide tiles around with a blank space. It's more complex (and typically involves BFS to solve), but it shares the idea of moving pieces into a blank. In our problem, we effectively had a 1D puzzle with specific movement rules. The sliding puzzle generalizes this to a grid and any tile can move into the blank.
Other String Transformation Problems: There are other string transformation challenges (for example, those involving swapping characters or using stack operations to achieve a target string). While not directly related in terms of rules, practicing various transformation problems helps build intuition. Always pay attention to what operations are allowed and how that constrains the transformation.