Move Pieces to Obtain a String

Med

#2129Time: O(N), where N is the length of the strings. Filtering strings, collecting indices, and comparing them each take linear time.Space: O(N), for storing the filtered strings and the lists of indices. In the worst case, where there are no blank spaces, these data structures will be proportional to the input size N.

Patterns

Two Pointers

Data structures

String

Prompt

You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where:

The characters '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.
The character '_' 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.length
1 <= n <= 10⁵
start and target consist of the characters 'L', 'R', and '_'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach breaks the problem into two main parts. First, it confirms that the relative order of 'L' and 'R' pieces is the same in both start and target strings. Second, it verifies that each piece's move is valid according to the rules ('L' only moves left, 'R' only moves right). This is done by collecting the indices of all pieces and comparing them.

Algorithm

Create two new strings by removing all _ characters from start and target.
If these new strings are not identical, return false.
Create four lists to store the indices of 'L' and 'R' characters for both start and target strings.
Populate these lists by iterating through the original strings.
Compare the indices for each corresponding 'L' piece. The index in start must be greater than or equal to the index in target. If not, return false.
Compare the indices for each corresponding 'R' piece. The index in start must be less than or equal to the index in target. If not, return false.
If all checks pass, return true.

Walkthrough

The fundamental insight is that the pieces ('L' and 'R') cannot cross each other. This implies that if we remove all the blank spaces ('_'), the resulting sequence of pieces must be identical for both start and target. We can check this by creating filtered versions of the strings. For example, start.replace("_", "").equals(target.replace("_", "")). If this condition fails, it's impossible to transform start to target.

If the piece sequences are the same, we then need to check the movement constraints. An 'L' piece at an initial index i can only end up at a final index j where j <= i. Conversely, an 'R' piece at index i can only move to an index j where j >= i. To verify this for all pieces, we can gather the indices of all 'L's and 'R's from both strings into separate lists. Then, we compare the indices of corresponding pieces. For the k-th 'L' piece, its index in start must be greater than or equal to its index in target. For the k-th 'R' piece, its index in start must be less than or equal to its index in target. If any piece violates these rules, the transformation is impossible.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public boolean canChange(String start, String target) {6        if (!start.replace("_", "").equals(target.replace("_", ""))) {7            return false;8        }9 10        int n = start.length();11        List<Integer> startLIndices = new ArrayList<>();12        List<Integer> startRIndices = new ArrayList<>();13        List<Integer> targetLIndices = new ArrayList<>();14        List<Integer> targetRIndices = new ArrayList<>();15 16        for (int i = 0; i < n; i++) {17            if (start.charAt(i) == 'L') {18                startLIndices.add(i);19            } else if (start.charAt(i) == 'R') {20                startRIndices.add(i);21            }22            if (target.charAt(i) == 'L') {23                targetLIndices.add(i);24            } else if (target.charAt(i) == 'R') {25                targetRIndices.add(i);26            }27        }28 29        for (int i = 0; i < startLIndices.size(); i++) {30            if (startLIndices.get(i) < targetLIndices.get(i)) {31                return false;32            }33        }34 35        for (int i = 0; i < startRIndices.size(); i++) {36            if (startRIndices.get(i) > targetRIndices.get(i)) {37                return false;38            }39        }40 41        return true;42    }43}

Complexity

Time

O(N), where N is the length of the strings. Filtering strings, collecting indices, and comparing them each take linear time.

Space

O(N), for storing the filtered strings and the lists of indices. In the worst case, where there are no blank spaces, these data structures will be proportional to the input size N.

Trade-offs

Pros

Conceptually simple and easy to understand.
The logic is broken down into two distinct, verifiable steps.

Cons

Uses O(N) extra space, which can be inefficient for very long strings.
Requires multiple passes over the data.

This highly efficient approach solves the problem in a single pass using two pointers and constant extra space. The pointers traverse the start and target strings, skipping blank spaces to find corresponding pieces. At each step, it simultaneously verifies that the piece types match (ensuring relative order is preserved) and that the move is valid based on the piece's position and movement rules.

Algorithm

Initialize two pointers, i for start and j for target, both at 0.
Loop as long as either pointer is within the string bounds (i < n or j < n).
Inside the loop, advance i and j past any _ characters.
If both pointers reach the end of the strings, return true.
If only one pointer reaches the end, it means the piece counts differ, so return false.
Check if the pieces at start[i] and target[j] are different. If so, return false.
Check the movement rules: if it's an 'L' piece and i < j, return false. If it's an 'R' piece and i > j, return false.
Increment both i and j to process the next pair of pieces.

Walkthrough

This optimal solution is built on the same logical foundations as the two-pass approach but achieves constant space complexity by avoiding intermediate data structures. It uses two pointers, i for the start string and j for the target string, to find and compare corresponding non-blank characters in one go.

The pointers i and j are advanced to skip any _ characters. When both pointers land on a piece, we perform a series of checks:

Piece Count Mismatch: If one pointer reaches the end of its string while the other has not, it implies an unequal number of pieces, making the transformation impossible.
Relative Order Mismatch: If start.charAt(i) is not equal to target.charAt(j), the relative order of pieces has changed, which is not allowed.
Movement Rule Violation:
- If the piece is 'L', it must not move right. Therefore, its starting index i must be greater than or equal to its target index j. An i < j condition is invalid.
- If the piece is 'R', it must not move left. Therefore, its starting index i must be less than or equal to its target index j. An i > j condition is invalid.

If any of these checks fail, we return false. Otherwise, we advance both pointers to find the next pair of pieces. If the entire strings are traversed without any violations, it means the transformation is possible, and we return true.

1class Solution {2    public boolean canChange(String start, String target) {3        int n = start.length();4        int i = 0; // pointer for start5        int j = 0; // pointer for target6 7        while (i < n || j < n) {8            while (i < n && start.charAt(i) == '_') {9                i++;10            }11            while (j < n && target.charAt(j) == '_') {12                j++;13            }14 15            if (i == n && j == n) {16                return true;17            }18            if (i == n || j == n) {19                return false;20            }21 22            if (start.charAt(i) != target.charAt(j)) {23                return false;24            }25 26            char piece = start.charAt(i);27            if (piece == 'L') {28                if (i < j) {29                    return false;30                }31            } else { // piece == 'R'32                if (i > j) {33                    return false;34                }35            }36            37            i++;38            j++;39        }40 41        return true;42    }43}

Complexity

Time

O(N), where N is the length of the strings. Each pointer traverses its respective string exactly once.

Space

O(1). The solution uses only a constant amount of extra space for the two pointers, regardless of the input size.

Trade-offs

Pros

Extremely efficient with O(1) space complexity.
Solves the problem in a single pass over the input strings.

Cons

The combined logic within a single loop can be slightly more complex to grasp initially compared to a multi-pass approach.

Solutions

Solution

1class Solution {2public3  boolean canChange(String start, String target) {4    List<int[]> a = f(start);5    List<int[]> b = f(target);6    if (a.size() != b.size()) {7      return false;8    }9    for (int i = 0; i < a.size(); ++i) {10      int[] x = a.get(i);11      int[] y = b.get(i);12      if (x[0] != y[0]) {13        return false;14      }15      if (x[0] == 1 && x[1] < y[1]) {16        return false;17      }18      if (x[0] == 2 && x[1] > y[1]) {19        return false;20      }21    }22    return true;23  }24private25  List<int[]> f(String s) {26    List<int[]> res = new ArrayList<>();27    for (int i = 0; i < s.length(); ++i) {28      if (s.charAt(i) == 'L') {29        res.add(new int[]{1, i});30      } else if (s.charAt(i) == 'R') {31        res.add(new int[]{2, i});32      }33    }34    return res;35  }36}

1using pii = pair < int , int > ; class Solution { public: bool canChange ( string start , string target ) { auto a = f ( start ); auto b = f ( target ); if ( a . size () != b . size ()) return false ; for ( int i = 0 ; i < a . size (); ++ i ) { auto x = a [ i ], y = b [ i ]; if ( x . first != y . first ) return false ; if ( x . first == 1 && x . second < y . second ) return false ; if ( x . first == 2 && x . second > y . second ) return false ; } return true ; } vector < pair < int , int >> f ( string s ) { vector < pii > res ; for ( int i = 0 ; i < s . size (); ++ i ) { if ( s [ i ] == 'L' ) res . push_back ({ 1 , i }); else if ( s [ i ] == 'R' ) res . push_back ({ 2 , i }); } return res ; } };

1class Solution:2    def canChange(self, start: str, target: str) -> bool: a = [(v, i) for i, v in enumerate(start) if v != '_'] b = [(v, i) for i, v in enumerate(target) if v != '_'] if len(a) != len(b): return False for (c, i), (d, j) in zip(a, b): if c != d: return False if c == 'L' and i < j: return False if c == 'R' and i > j: return False return True

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem