LeetCode 777: Swap Adjacent in LR String

Problem Restatement

We are given two strings, start and result.

Both strings contain only three characters:

We can make two kinds of moves:

XL -> LX
RX -> XR

The first move lets L move one step left.

The second move lets R move one step right.

Return True if we can transform start into result. Otherwise, return False.

Input and Output

Function shape:

class Solution:
    def canTransform(self, start: str, result: str) -> bool:
        ...

Examples

Example 1:

start = "RXXLRXRXL"
result = "XRLXXRRLX"

This returns:

True

One valid sequence is:

RXXLRXRXL
XRXLRXRXL
XRLXRXRXL
XRLXXRRXL
XRLXXRRLX

Example 2:

start = "X"
result = "L"

This returns:

False

The characters are different. We cannot create a new L.

Example 3:

start = "LXXLXRLXXL"
result = "XLLXRXLXLX"

This returns:

False

At least one L would need to move right, which is not allowed.

First Thought: Simulate Moves

One possible idea is to simulate all moves.

From start, we can repeatedly replace:

XL -> LX
RX -> XR

Then we check whether we can eventually reach result.

This is difficult because there may be many possible move orders. Trying all possibilities can grow very quickly.

Instead of generating transformations, we can validate whether the final arrangement is possible.

Problem With Simulation

The moves have simple direction rules:

So:

Also, L and R cannot pass through each other. They only move by swapping with X.

That means if we remove all X characters, the order of L and R must stay the same.

For example:

start = "RXL"
result = "LXR"

Ignoring X gives:

start  -> "RL"
result -> "LR"

The order changed, so the transformation is impossible.

Key Insight

There are two conditions.

First, after removing all X, both strings must have the same sequence of L and R.

start.replace("X", "") == result.replace("X", "")

Second, each piece must move only in its allowed direction.

For matching non-X characters:

Why?

L can only move left, so its final index cannot be greater than its start index.

R can only move right, so its final index cannot be less than its start index.

Algorithm

Use two pointers.

i scans start.

j scans result.

At each step:

1. Move i forward while start[i] == "X".
2. Move j forward while result[j] == "X".
3. If both pointers reached the end, return True.
4. If only one pointer reached the end, return False.
5. If start[i] != result[j], return False.
6. If the character is L, require i >= j.
7. If the character is R, require i <= j.
8. Move both pointers forward.

Correctness

The algorithm compares only the meaningful pieces, L and R.

Skipping X is valid because X represents empty space. The pieces that matter are the ordered sequence of L and R.

If the algorithm finds different non-X characters at matching positions, then the relative order of pieces differs between start and result. Since pieces cannot pass through each other, no valid move sequence can transform one string into the other.

If the matching piece is L, the algorithm checks that its start index is greater than or equal to its result index. This is necessary because L can only move left through moves of the form XL -> LX.

If the matching piece is R, the algorithm checks that its start index is less than or equal to its result index. This is necessary because R can only move right through moves of the form RX -> XR.

If every piece has the same relative order and every piece moves only in its allowed direction, then the required transformation is possible. Each L can be moved left through available X positions, and each R can be moved right through available X positions without crossing another non-X piece.

Therefore, the algorithm returns True exactly when the transformation is possible.

Complexity

Here, n is the length of the strings.

Implementation

class Solution:
    def canTransform(self, start: str, result: str) -> bool:
        n = len(start)
        i = 0
        j = 0

        while i < n or j < n:
            while i < n and start[i] == "X":
                i += 1

            while j < n and result[j] == "X":
                j += 1

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

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

            if start[i] != result[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

Code Explanation

We keep two pointers:

i = 0
j = 0

Pointer i scans start.

Pointer j scans result.

We skip empty spaces in both strings:

while i < n and start[i] == "X":
    i += 1

while j < n and result[j] == "X":
    j += 1

After skipping X, both pointers should either reach the end together or point to matching pieces.

If both reached the end, all pieces were matched:

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

If only one reached the end, one string has extra L or R pieces:

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

The next non-X pieces must match:

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

Then we enforce movement direction.

An L cannot move right:

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

An R cannot move left:

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

If all checks pass, we move to the next piece:

i += 1
j += 1

Testing

def run_tests():
    s = Solution()

    assert s.canTransform("RXXLRXRXL", "XRLXXRRLX") is True
    assert s.canTransform("X", "L") is False
    assert s.canTransform("LXXLXRLXXL", "XLLXRXLXLX") is False

    assert s.canTransform("XL", "LX") is True
    assert s.canTransform("LX", "XL") is False

    assert s.canTransform("RX", "XR") is True
    assert s.canTransform("XR", "RX") is False

    assert s.canTransform("XXRXXLXXXX", "XXXXRXXLXX") is True
    assert s.canTransform("RXL", "LXR") is False

    print("all tests passed")

run_tests()

Test coverage: