Move Pieces to Obtain a String

LeetCode 2337: Move Pieces to Obtain a String Solution & Explanation

Problem Overview

TL;DR: Use a two-pointer approach to verify that the sequence of 'L' and 'R' characters matches in both strings and that their indices satisfy the directional movement constraints (L moves left, R moves right).

In the LeetCode 2337 problem, "Move Pieces to Obtain a String", you are given two strings, start and target, consisting of 'L', 'R', and '_' (underscores representing empty spaces). The rules define that 'L' pieces can move to the left into adjacent empty spaces, and 'R' pieces can move to the right into adjacent empty spaces. The pieces cannot jump over each other. The goal is to determine if start can be transformed into target through any sequence of valid moves.

This is a popular interview question because it tests the ability to identify invariants in a simulation problem without actually performing the simulation.

Brute Force Approach for Move Pieces to Obtain a String

A naive brute force approach would attempt to simulate every possible valid move from the start state to see if the target state is reachable. This is typically modeled as a Breadth-First Search (BFS) or Depth-First Search (DFS) on the state space of the string.

Pseudo-code:

function canChange(start, target):
    queue = [start]
    visited = {start}
    
    while queue is not empty:
        current = queue.pop()
        if current == target:
            return true
            
        for every possible move in current:
            next_state = perform_move(current)
            if next_state not in visited:
                visited.add(next_state)
                queue.push(next_state)
                
    return false

Complexity Analysis:

• Time Complexity: Exponential. In the worst case, the number of states can be roughly proportional to the permutations of the string, which is enormous for $N=10^5$.
• Space Complexity: Exponential, to store the visited set.

Why it fails: The constraints specify $N \le 10^5$. A BFS approach will immediately hit a Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) error because the state space is too large to traverse. We need a linear time solution that checks validity without simulation.

Algorithm Strategy: Two Pointer Patterns

We utilize two pointers, i and j, to iterate through start and target respectively.

1. Initialization: Set both i and j to 0.
2. Traversal: Loop until we have processed both strings completely.
3. Skip Gaps: Inside the main loop, advance i as long as start[i] is an underscore. Similarly, advance j as long as target[j] is an underscore.
4. Completion Check: If one pointer reaches the end of the string while the other is still pointing to a valid character, the strings have a different number of pieces. Return false.
5. Character Match: If both pointers are within bounds, check if start[i] == target[j]. If they differ (e.g., 'L' vs 'R'), the relative order is broken. Return false.
6. Position Check:
   • If the character is 'L', ensure i >= j. If i < j, the 'L' would need to move right, which is invalid.
   • If the character is 'R', ensure i <= j. If i > j, the 'R' would need to move left, which is invalid.
7. Advance: Increment both i and j to process the next pieces.
8. Result: If the loop completes without returning false, return true.

Execution Flow

Consider start = "_L__R__R_", target = "L______RR".

1. Init: i=0, j=0.
2. Skip:
   • i moves to 1 (start[1] = 'L').
   • j stays at 0 (target[0] = 'L').
3. Check:
   • Characters match ('L' == 'L').
   • Constraint: 'L' requires i >= j. $1 \ge 0$ is True.
4. Advance: i becomes 2, j becomes 1.
5. Skip:
   • i moves to 4 (start[4] = 'R').
   • j moves to 7 (target[7] = 'R').
6. Check:
   • Characters match ('R' == 'R').
   • Constraint: 'R' requires i <= j. $4 \le 7$ is True.
7. Advance: i becomes 5, j becomes 8.
8. Skip:
   • i moves to 7 (start[7] = 'R').
   • j moves to 8 (target[8] = 'R').
9. Check:
   • Characters match ('R' == 'R').
   • Constraint: 'R' requires i <= j. $7 \le 8$ is True.
10. Advance: Both pointers exceed bounds (or reach end).
11. Return: true.

Proof of Correctness

The correctness rests on the fact that the conditions checked are both necessary and sufficient.

• Necessity: The problem explicitly forbids crossing (enforced by order check) and wrong-way movement (enforced by index comparison). If any check fails, the transformation is impossible.
• Sufficiency: If the relative order is preserved and every individual piece can physically move to its target position without direction violation, the underscores "between" them can essentially be ignored. Since no piece blocks another (due to order preservation), the moves are valid.

Pattern Reuse Notes

The Two Pointer pattern used here is fundamental for array and string manipulation. It appears in various forms:

• LeetCode 26: Remove Duplicates from Sorted Array: Uses a "read" and "write" pointer to filter arrays in-place.
• LeetCode 27: Remove Element: Similar filtering logic, skipping specific values.
• LeetCode 75: Sort Colors: Uses three pointers to partition an array, a more complex variation of the linear scan.
• LeetCode 80: Remove Duplicates from Sorted Array II: Extends the logic of LeetCode 26 with a counter constraint.

In all these cases, the core strategy involves traversing the data linearly to enforce a specific structure or invariant without using extra space.

Reference Implementation

C++ Solution for LeetCode 2337

1class Solution {
2public:
3    bool canChange(string start, string target) {
4        int n = start.length();
5        int i = 0, j = 0;
6
7        while (i < n || j < n) {
8            // Skip underscores in start
9            while (i < n && start[i] == '_') {
10                i++;
11            }
12            // Skip underscores in target
13            while (j < n && target[j] == '_') {
14                j++;
15            }
16
17            // If one reaches end and other doesn't, count mismatch
18            if (i == n || j == n) {
19                return i == n && j == n;
20            }
21
22            // Check if pieces match
23            if (start[i] != target[j]) {
24                return false;
25            }
26
27            // Check directional constraints
28            if (start[i] == 'L' && i < j) {
29                return false; // 'L' cannot move right
30            }
31            if (start[i] == 'R' && i > j) {
32                return false; // 'R' cannot move left
33            }
34
35            // Move to next potential piece
36            i++;
37            j++;
38        }
39
40        return true;
41    }
42};

Java Solution for LeetCode 2337

1class Solution {
2    public boolean canChange(String start, String target) {
3        int n = start.length();
4        int i = 0;
5        int j = 0;
6
7        while (i < n || j < n) {
8            // Skip underscores in start
9            while (i < n && start.charAt(i) == '_') {
10                i++;
11            }
12            // Skip underscores in target
13            while (j < n && target.charAt(j) == '_') {
14                j++;
15            }
16
17            // If one string is exhausted, both must be exhausted
18            if (i == n || j == n) {
19                return i == n && j == n;
20            }
21
22            // Check if the current pieces are different
23            if (start.charAt(i) != target.charAt(j)) {
24                return false;
25            }
26
27            // Check constraints for 'L' (can only move left)
28            if (start.charAt(i) == 'L' && i < j) {
29                return false;
30            }
31            // Check constraints for 'R' (can only move right)
32            if (start.charAt(i) == 'R' && i > j) {
33                return false;
34            }
35
36            i++;
37            j++;
38        }
39
40        return true;
41    }
42}

Python Solution for LeetCode 2337

1class Solution:
2    def canChange(self, start: str, target: str) -> bool:
3        n = len(start)
4        i, j = 0, 0
5        
6        while i < n or j < n:
7            # Skip underscores in start
8            while i < n and start[i] == '_':
9                i += 1
10            
11            # Skip underscores in target
12            while j < n and target[j] == '_':
13                j += 1
14            
15            # If one pointer reaches the end, both must reach the end
16            if i == n or j == n:
17                return i == n and j == n
18            
19            # Check if pieces match
20            if start[i] != target[j]:
21                return false
22            
23            # Check 'L' constraint: cannot move right (i must be >= j)
24            if start[i] == 'L' and i < j:
25                return False
26                
27            # Check 'R' constraint: cannot move left (i must be <= j)
28            if start[i] == 'R' and i > j:
29                return False
30            
31            # Move to next
32            i += 1
33            j += 1
34            
35        return True