# LeetCode 777: Swap Adjacent in LR String

## Problem Restatement

We are given two strings, `start` and `result`.

Both strings contain only three characters:

| Character | Meaning |
|---|---|
| `L` | A piece that can move left |
| `R` | A piece that can move right |
| `X` | An empty space |

We can make two kinds of moves:

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

| Item | Meaning |
|---|---|
| Input | Two strings `start` and `result` |
| Output | `True` if the transformation is possible, otherwise `False` |
| Characters | Only `L`, `R`, and `X` |
| Length | `start.length == result.length` |

Function shape:

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

## Examples

Example 1:

```python
start = "RXXLRXRXL"
result = "XRLXXRRLX"
```

This returns:

```python
True
```

One valid sequence is:

```text
RXXLRXRXL
XRXLRXRXL
XRLXRXRXL
XRLXXRRXL
XRLXXRRLX
```

Example 2:

```python
start = "X"
result = "L"
```

This returns:

```python
False
```

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

Example 3:

```python
start = "LXXLXRLXXL"
result = "XLLXRXLXLX"
```

This returns:

```python
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:

```text
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:

| Move | Effect |
|---|---|
| `XL -> LX` | `L` moves left |
| `RX -> XR` | `R` moves right |

So:

| Character | Can move |
|---|---|
| `L` | Left only |
| `R` | Right only |

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:

```python
start = "RXL"
result = "LXR"
```

Ignoring `X` gives:

```python
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`.

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

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

For matching non-`X` characters:

| Character | Start index | Result index | Valid when |
|---|---:|---:|---|
| `L` | `i` | `j` | `i >= j` |
| `R` | `i` | `j` | `i <= j` |

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each pointer moves from left to right once |
| Space | `O(1)` | Only two indices are stored |

Here, `n` is the length of the strings.

## Implementation

```python
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:

```python
i = 0
j = 0
```

Pointer `i` scans `start`.

Pointer `j` scans `result`.

We skip empty spaces in both strings:

```python
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:

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

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

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

The next non-`X` pieces must match:

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

Then we enforce movement direction.

An `L` cannot move right:

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

An `R` cannot move left:

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

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

```python
i += 1
j += 1
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `"RXXLRXRXL"` to `"XRLXXRRLX"` | Standard valid transformation |
| `"X"` to `"L"` | Cannot create a new piece |
| Complex invalid case | Checks direction constraints |
| `"XL"` to `"LX"` | Single valid `L` move |
| `"LX"` to `"XL"` | Invalid `L` moving right |
| `"RX"` to `"XR"` | Single valid `R` move |
| `"XR"` to `"RX"` | Invalid `R` moving left |
| `"RXL"` to `"LXR"` | Detects changed `L/R` order |