Pseudo-code:

text
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.

Core Insight for Move Pieces to Obtain a String

The key intuition for the optimal LeetCode 2337 solution relies on two fundamental physical constraints enforced by the problem rules:

1. Relative Order Invariant: Since 'L' and 'R' pieces cannot jump over each other, their relative order must remain constant. If we remove all underscores from both start and target, the resulting strings must be identical. For example, if start has the sequence "L...R" and target has "R...L", transformation is impossible.
2. Directional Constraint:
   • An 'L' piece can only move left. Therefore, for any specific 'L', its index in start must be greater than or equal to its index in target (index_start >= index_target). If the 'L' starts at index 3 and needs to be at index 5, it's impossible because 'L' cannot move right.
   • An 'R' piece can only move right. Therefore, for any specific 'R', its index in start must be less than or equal to its index in target (index_start <= index_target).

Visual Description: Imagine two pointers, one for each string. As they traverse from left to right, they skip all underscores. When both pointers land on a character ('L' or 'R'), those characters must match. Furthermore, based on the character type, we check the indices. If start has an 'L' at index 5, and the corresponding 'L' in target is at index 2, the move is valid (5 -> 2 is left). If the target 'L' was at index 7, it would be invalid.

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.

Reference Implementation

C++ Solution for LeetCode 2337

cpp
class Solution {
public:
    bool canChange(string start, string target) {
        int n = start.length();
        int i = 0, j = 0;

        while (i < n || j < n) {
            // Skip underscores in start
            while (i < n && start[i] == '_') {
                i++;
            }
            // Skip underscores in target
            while (j < n && target[j] == '_') {
                j++;
            }

            // If one reaches end and other doesn't, count mismatch
            if (i == n || j == n) {
                return i == n && j == n;
            }

            // Check if pieces match
            if (start[i] != target[j]) {
                return false;
            }

            // Check directional constraints
            if (start[i] == 'L' && i < j) {
                return false; // 'L' cannot move right
            }
            if (start[i] == 'R' && i > j) {
                return false; // 'R' cannot move left
            }

            // Move to next potential piece
            i++;
            j++;
        }

        return true;
    }
};

Java Solution for LeetCode 2337

java
class Solution {
    public boolean canChange(String start, String target) {
        int n = start.length();
        int i = 0;
        int j = 0;

        while (i < n || j < n) {
            // Skip underscores in start
            while (i < n && start.charAt(i) == '_') {
                i++;
            }
            // Skip underscores in target
            while (j < n && target.charAt(j) == '_') {
                j++;
            }

            // If one string is exhausted, both must be exhausted
            if (i == n || j == n) {
                return i == n && j == n;
            }

            // Check if the current pieces are different
            if (start.charAt(i) != target.charAt(j)) {
                return false;
            }

            // Check constraints for 'L' (can only move left)
            if (start.charAt(i) == 'L' && i < j) {
                return false;
            }
            // Check constraints for 'R' (can only move right)
            if (start.charAt(i) == 'R' && i > j) {
                return false;
            }

            i++;
            j++;
        }

        return true;
    }
}

Python Solution for LeetCode 2337

python
class Solution:
    def canChange(self, start: str, target: str) -> bool:
        n = len(start)
        i, j = 0, 0
        
        while i < n or j < n:
            # Skip underscores in start
            while i < n and start[i] == '_':
                i += 1
            
            # Skip underscores in target
            while j < n and target[j] == '_':
                j += 1
            
            # If one pointer reaches the end, both must reach the end
            if i == n or j == n:
                return i == n and j == n
            
            # Check if pieces match
            if start[i] != target[j]:
                return false
            
            # Check 'L' constraint: cannot move right (i must be >= j)
            if start[i] == 'L' and i < j:
                return False
                
            # Check 'R' constraint: cannot move left (i must be <= j)
            if start[i] == 'R' and i > j:
                return False
            
            # Move to next
            i += 1
            j += 1
            
        return True