LeetCode 2337 - Move Pieces to Obtain a String

LeetCode Problem 2337

Difficulty: 🟡 Medium
Topics: Two Pointers, String

Solution

Problem Understanding

The problem gives us two strings, start and target, both having the same length. Each position in the strings contains one of three characters:

• 'L', representing a piece that can only move left
• 'R', representing a piece that can only move right
• '_', representing an empty space

A move consists of sliding a piece into an adjacent blank space, subject to the movement restrictions:

• 'L' may only move left
• 'R' may only move right

The task is to determine whether it is possible to transform start into target using any number of valid moves.

The important detail is that pieces cannot jump over each other. Every movement happens one step at a time into an adjacent blank space. Because of this, the relative ordering of the non-blank pieces can never change.

For example, if the non-blank sequence in start is "LRR" and the non-blank sequence in target is "RLR", the transformation is impossible because the order of pieces differs.

The constraints are important:

• n can be as large as 10^5
• This rules out expensive simulation approaches
• We need a linear or near-linear algorithm

Several edge cases can cause bugs in naive implementations:

• An 'L' attempting to move right
• An 'R' attempting to move left
• Different ordering of non-blank pieces
• Strings containing only blanks
• Multiple consecutive blanks
• Pieces blocked by other pieces

The problem guarantees that both strings contain only 'L', 'R', and '_', and that they have equal length.

Approaches

Brute Force Approach

A brute-force solution would simulate all possible valid moves from the start string until either:

• We reach target
• No more states are possible

This can be implemented using BFS or DFS over all reachable configurations.

The approach is correct because it explores every legal transformation. If target is reachable, eventually the search will discover it.

However, this method is extremely inefficient. Each position may generate multiple future states, and the number of configurations grows exponentially with the string length. For n = 10^5, this is completely infeasible.

The brute-force approach also wastes work because it repeatedly simulates movements that can instead be reasoned about directly using positional constraints.

Optimal Two Pointers Approach

The key observation is that the relative order of the non-blank pieces never changes.

If we remove all '_' characters:

• start and target must contain the same sequence of 'L' and 'R'
• Otherwise transformation is impossible

Next, we analyze movement constraints:

• 'L' can only move left, so its target index must be less than or equal to its starting index
• 'R' can only move right, so its target index must be greater than or equal to its starting index

We can verify these conditions efficiently using two pointers:

• One pointer scans start
• One pointer scans target
• Both skip blank spaces
• When pieces are found, compare their types and positions

This avoids simulation entirely and runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all reachable states
Optimal	O(n)	O(1)	Uses positional constraints with two pointers

Algorithm Walkthrough

1. Initialize two pointers, i for start and j for target.
2. Move pointer i forward until it points to a non-blank character or reaches the end of the string. This skips positions that do not affect piece ordering.
3. Move pointer j forward until it points to a non-blank character or reaches the end.
4. If both pointers reach the end simultaneously, all pieces matched successfully, so return True.
5. If only one pointer reaches the end, the strings contain different numbers of pieces, so return False.
6. Compare the characters at start[i] and target[j].

• If they differ, the ordering of pieces changed, which is impossible.
• Return False.

7. If the character is 'L', verify that i >= j.

• 'L' can only move left.
• If i < j, the piece would need to move right, which is invalid.

8. If the character is 'R', verify that i <= j.

• 'R' can only move right.
• If i > j, the piece would need to move left, which is invalid.

9. Move both pointers forward and repeat the process.
10. If all pieces satisfy the constraints, return True.

Why it works

The algorithm relies on two invariants:

• The relative order of non-blank pieces never changes
• Each piece type has a strict movement direction

By matching corresponding non-blank pieces and checking their allowable positional movement, we fully characterize whether the transformation is possible. No actual movement simulation is required.

Python Solution

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        n = len(start)

        i = 0
        j = 0

        while i < n or j < n:
            while i < n and start[i] == '_':
                i += 1

            while j < n and target[j] == '_':
                j += 1

            if i == n and j == n:
                return True

            if i == n or j == n:
                return False

            if start[i] != target[j]:
                return False

            if start[i] == 'L' and i < j:
                return False

            if start[i] == 'R' and i > j:
                return False

            i += 1
            j += 1

        return True

The implementation follows the exact logic described in the algorithm walkthrough.

The variables i and j scan through start and target. Blank spaces are skipped because they do not represent actual pieces.

After locating corresponding pieces, the code first checks whether the characters match. This ensures that the order of non-blank pieces is identical.

Next, the movement constraints are verified:

• 'L' cannot move right
• 'R' cannot move left

If any constraint is violated, the function immediately returns False.

If all pieces pass the checks, the transformation is possible and the function returns True.

Go Solution

func canChange(start string, target string) bool {
	n := len(start)

	i := 0
	j := 0

	for i < n || j < n {
		for i < n && start[i] == '_' {
			i++
		}

		for j < n && target[j] == '_' {
			j++
		}

		if i == n && j == n {
			return true
		}

		if i == n || j == n {
			return false
		}

		if start[i] != target[j] {
			return false
		}

		if start[i] == 'L' && i < j {
			return false
		}

		if start[i] == 'R' && i > j {
			return false
		}

		i++
		j++
	}

	return true
}

The Go implementation is nearly identical to the Python version.

Since Go strings are byte-indexable and the input contains only ASCII characters, indexing with start[i] and target[j] is safe and efficient.

No additional memory allocation is required, so the solution maintains constant auxiliary space.

Worked Examples

Example 1

start  = "_L__R__R_"
target = "L______RR"

Step-by-step Trace

Step	i	j	start[i]	target[j]	Result
Skip blanks	1	0	L	L	Match
Check L movement	1	0	L	L	Valid because 1 >= 0
Next piece	4	7	R	R	Match
Check R movement	4	7	R	R	Valid because 4 <= 7
Next piece	7	8	R	R	Match
Check R movement	7	8	R	R	Valid because 7 <= 8
End reached	9	9	-	-	Return True

Final result: True

Example 2

start  = "R_L_"
target = "__LR"

Step-by-step Trace

Step	i	j	start[i]	target[j]	Result
First piece	0	2	R	L	Different pieces

Since the non-blank sequences differ, transformation is impossible.

Final result: False

Example 3

start  = "_R"
target = "R_"

Step-by-step Trace

Step	i	j	start[i]	target[j]	Result
First piece	1	0	R	R	Match
Check R movement	1	0	R	R	Invalid because 1 > 0

The 'R' piece would need to move left.

Final result: False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer traverses the string at most once
Space	O(1)	Only a few integer variables are used

The algorithm is linear because every character in both strings is visited at most once. The nested loops only skip blanks, and no character is revisited after a pointer advances.

The space complexity is constant because the solution does not allocate additional data structures proportional to the input size.

Test Cases

solution = Solution()

assert solution.canChange("_L__R__R_", "L______RR") == True
# Basic valid transformation

assert solution.canChange("R_L_", "__LR") == False
# Different non-blank ordering

assert solution.canChange("_R", "R_") == False
# R cannot move left

assert solution.canChange("L_", "_L") == False
# L cannot move right

assert solution.canChange("_L", "L_") == True
# L moving left

assert solution.canChange("R_", "_R") == True
# R moving right

assert solution.canChange("___", "___") == True
# Only blanks

assert solution.canChange("LR", "LR") == True
# Already equal

assert solution.canChange("RL", "LR") == False
# Order changes

assert solution.canChange("_R_L_", "__RL_") == False
# R would need to move left

assert solution.canChange("__L__", "L____") == True
# L moving multiple spaces left

assert solution.canChange("____R", "R____") == False
# R cannot move left across blanks

assert solution.canChange("L_R", "LR_") == False
# R would need to move left

assert solution.canChange("_LR__", "L_R__") == True
# Valid mixed movement

assert solution.canChange("___L___R__", "L______ _R_".replace(" ", "")) == True
# Multiple long-distance valid moves

Test	Why
_L__R__R_ -> L______RR	Standard valid transformation
R_L_ -> __LR	Detects ordering mismatch
_R -> R_	Verifies R cannot move left
L_ -> _L	Verifies L cannot move right
_L -> L_	Valid left movement
R_ -> _R	Valid right movement
___ -> ___	All blank edge case
LR -> LR	Already equal
RL -> LR	Relative ordering changed
_R_L_ -> __RL_	Illegal R movement
__L__ -> L____	Long-distance left movement
____R -> R____	Long-distance illegal movement
L_R -> LR_	R attempting left movement
_LR__ -> L_R__	Mixed valid moves
___L___R__ -> L_______R_	Large blank regions

Edge Cases

Different Non-Blank Ordering

A common mistake is checking only whether pieces can physically move to target positions without verifying order preservation.

For example:

start  = "RL"
target = "LR"

Even though both strings contain one 'L' and one 'R', the transformation is impossible because pieces cannot pass through each other.

The implementation handles this by directly comparing corresponding non-blank characters during traversal.

'L' Moving Right

An 'L' piece can only move left.

Example:

start  = "L_"
target = "_L"

The target position is to the right of the starting position, which violates the movement rule.

The implementation checks:

if start[i] == 'L' and i < j:
    return False

This immediately rejects illegal rightward movement.

'R' Moving Left

An 'R' piece can only move right.

Example:

start  = "_R"
target = "R_"

The target position is to the left of the starting position.

The implementation detects this using:

if start[i] == 'R' and i > j:
    return False

This prevents invalid leftward movement.

Strings Containing Only Blanks

Another subtle edge case is when both strings contain only '_'.

Example:

start  = "___"
target = "___"

There are no pieces to compare, so the transformation is trivially valid.

The implementation correctly handles this because both pointers eventually reach the end simultaneously, causing the algorithm to return True.