#2337

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Move Pieces to Obtain a String

Determine if the pieces in start can be moved to form target using two-pointer scanning and strict left-right movement rules.

two pointers string

Problem Statement

You are given two strings, start and target, each of length n, consisting of the characters 'L', 'R', and ''. Pieces labeled 'L' can only move to the left, 'R' can only move to the right, and ' ' represents an empty space.

Return true if it is possible to move the pieces in start any number of times to match target exactly. Otherwise, return false. For example, start = "L__R__R " and target = "L______RR" should return true, while start = "R_L_" and target = "__LR" should return false.

Examples

Example 1

Input: start = "_L__R__R_", target = "L______RR"

Output: true

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

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

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 <= 105
start and target consist of the characters 'L', 'R', and '_'.

Solution Approach

Two-Pointer Scanning

Initialize two pointers for start and target. Skip all underscores while scanning and align pieces. Compare corresponding characters to ensure they match and obey movement constraints.

Validate Movement Constraints

For each 'L' piece, ensure its position in start is not to the right of target. For each 'R' piece, ensure its position in start is not to the left of target. If any piece violates this, return false immediately.

Check Complete Alignment

After scanning all non-underscore characters, confirm both pointers reach the end. If extra movable pieces remain unmatched, the transformation is impossible.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) since each string is scanned once. Space complexity is O(1) as only two pointers are used, with no extra arrays or data structures.

What Interviewers Usually Probe

They may ask about moving 'L' pieces left versus 'R' pieces right.
They may hint at scanning both strings simultaneously to maintain order invariants.
They may test edge cases with consecutive underscores or overlapping movement.

Common Pitfalls or Variants

Common pitfalls

Ignoring the direction constraints of 'L' and 'R' pieces and assuming free movement.
Failing to skip underscores correctly when aligning pointers in both strings.
Not checking that extra unmatched pieces remain at the end after scanning.

Follow-up variants

Allow diagonal or bidirectional movement and see how constraints change.
Check transformations with multiple identical pieces in sequence to test order preservation.
Consider using a queue to simulate piece movements instead of two pointers.

FAQ

Can underscores move in Move Pieces to Obtain a String?

No, underscores represent empty spaces and cannot move; they simply allow pieces to slide into them.

Why is the two-pointer pattern used here?

Two-pointer scanning efficiently checks corresponding non-underscore characters in start and target while preserving order and enforcing movement constraints.

What happens if an 'L' piece is to the right of its target position?

It is impossible to move 'L' left past its target, so the function should immediately return false.

Does the order of 'L' and 'R' pieces matter?

Yes, the relative order must remain consistent because 'L' can only move left and 'R' can only move right, preventing crossing.

What is the space complexity for this solution?

Space complexity is O(1) because only two pointers are used, with no extra arrays or data structures.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    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

Continue Practicing

#2472 maximum number of non overlapping palindrome substrings #2193 minimum number of moves to make palindrome #2486 append characters to string to make subsequence