# Swap Adjacent in LR String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/swap-adjacent-in-lr-string)
Canonical: https://scaleengineer.com/dsa/problems/swap-adjacent-in-lr-string
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
---
## Problem
In a string composed of `'L'`, `'R'`, and `'X'` characters, like `"RXXLRXRXL"`, a move consists of either replacing one occurrence of `"XL"` with `"LX"`, or replacing one occurrence of `"RX"` with `"XR"`. Given the starting string `start` and the ending string `result`, return `True` if and only if there exists a sequence of moves to transform `start` to `result`.

**Example 1:**

**Input:** start = "RXXLRXRXL", result = "XRLXXRRLX"
**Output:** true
**Explanation:** We can transform start to result following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

**Example 2:**

**Input:** start = "X", result = "L"
**Output:** false

**Constraints:**

* `1 <= start.length <= 104`
* `start.length == result.length`
* Both `start` and `result` will only consist of characters in `'L'`, `'R'`, and `'X'`.

# Approaches
## Two-Pass Approach
This approach is based on observing the key properties of the allowed moves. The moves `XL -> LX` and `RX -> XR` imply that 'L' characters can only move left past 'X's, and 'R' characters can only move right past 'X's. Crucially, 'L' and 'R' can never move past each other. This leads to two main conditions that must be true for a transformation to be possible:

1.  The sequence of 'L's and 'R's, ignoring 'X's, must be the same in both `start` and `result`.
2.  Each 'L' in `start` must end up at an index less than or equal to its starting index. Each 'R' must end up at an index greater than or equal to its starting index.

This approach verifies these two conditions in two separate passes over the strings.
**Time:** O(N). The `replace` operation takes O(N) time. The subsequent passes to collect and compare indices also take O(N) time. Thus, the total time complexity is linear. · **Space:** O(N), where N is the length of the strings. In the worst case, the strings might contain no 'X's, so the filtered strings and the index lists can take up space proportional to N.
**Pros:** The logic is straightforward and directly follows from the problem's constraints.; It's relatively easy to implement and debug.
**Cons:** Requires extra space proportional to the length of the strings to store the filtered strings and the lists of indices.
### Explanation
The algorithm is implemented in two main steps:

1.  **Check Relative Order:** We first create two new strings by removing all 'X' characters from `start` and `result`. If these two new strings are not equal, it means the relative order of 'L's and 'R's is different, so we can immediately return `false`. This check efficiently confirms that the counts and sequence of non-'X' characters are the same.

2.  **Check Positional Constraints:** If the first check passes, we proceed to verify the movement rules. We iterate through the `start` and `result` strings to collect the indices of all 'L's and 'R's. We store these indices in four lists: `l_start_indices`, `r_start_indices`, `l_result_indices`, and `r_result_indices`. Then, we compare the indices for each corresponding character:
    - For each `i`-th 'L', we check if `l_start_indices[i] >= l_result_indices[i]`.
    - For each `i`-th 'R', we check if `r_start_indices[i] <= r_result_indices[i]`.
    If any of these conditions are violated, we return `false`. If all checks pass, the transformation is possible, and we return `true`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean canTransform(String start, String result) {
        if (!start.replace("X", "").equals(result.replace("X", ""))) {
            return false;
        }

        List<Integer> lStartIndices = new ArrayList<>();
        List<Integer> rStartIndices = new ArrayList<>();
        for (int i = 0; i < start.length(); i++) {
            if (start.charAt(i) == 'L') {
                lStartIndices.add(i);
            } else if (start.charAt(i) == 'R') {
                rStartIndices.add(i);
            }
        }

        List<Integer> lResultIndices = new ArrayList<>();
        List<Integer> rResultIndices = new ArrayList<>();
        for (int i = 0; i < result.length(); i++) {
            if (result.charAt(i) == 'L') {
                lResultIndices.add(i);
            } else if (result.charAt(i) == 'R') {
                rResultIndices.add(i);
            }
        }

        for (int i = 0; i < lStartIndices.size(); i++) {
            if (lStartIndices.get(i) < lResultIndices.get(i)) {
                return false;
            }
        }

        for (int i = 0; i < rStartIndices.size(); i++) {
            if (rStartIndices.get(i) > rResultIndices.get(i)) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- First, check a fundamental invariant: the relative ordering of 'L' and 'R' characters cannot change. This is because 'L' and 'R' cannot move past each other. We can verify this by removing all 'X's from both `start` and `result` strings and checking if the resulting strings are identical. If not, transformation is impossible.
- If the first check passes, it means both strings have the same number and sequence of 'L's and 'R's. Now, we must check if the movements are valid.
- The move `XL -> LX` means an 'L' can only move to the left. Therefore, for any k-th 'L' character, its index in the `start` string must be greater than or equal to its index in the `result` string.
- The move `RX -> XR` means an 'R' can only move to the right. Therefore, for any k-th 'R' character, its index in the `start` string must be less than or equal to its index in the `result` string.
- To implement this, we can perform a second pass to collect the indices of all 'L's and 'R's from both strings into separate lists.
- Finally, we compare these lists of indices pair-wise to ensure the movement conditions are met.

## One-Pass Two-Pointer Approach
This approach optimizes the two-pass method by combining all necessary checks into a single pass over the strings. It uses two pointers to simultaneously iterate through the `start` and `result` strings, comparing non-'X' characters as they are found. This avoids the need for intermediate data structures like new strings or lists of indices, thus reducing the space complexity to be constant.
**Time:** O(N), where N is the length of the strings. Each pointer, `i` and `j`, traverses its respective string at most once. · **Space:** O(1). We only use a few variables to store the pointers, regardless of the input size.
**Pros:** Extremely efficient, using only a single pass through the data.; Optimal space complexity, as it uses only O(1) extra space.
**Cons:** The logic, while efficient, can be slightly more complex to grasp initially compared to the two-pass method due to the combined checks and pointer manipulation.
### Explanation
We can think of the 'X's as empty spaces. The core idea is to match the non-'X' characters of `start` and `result` in order and verify their movement rules on the fly.

We use two pointers, `i` and `j`, to scan `start` and `result` respectively. In each step, we advance both pointers past any 'X's to find the next 'L' or 'R'.

Once we find a non-'X' character in both strings (at `start[i]` and `result[j]`), we first check if they are the same character. If not (`start[i] != result[j]`), it means the relative order of 'L's and 'R's is broken, so we return `false`.

If the characters match, we check the positional constraints:
- If `start[i] == 'L'`, it must have moved left or stayed put. This implies its starting index `i` must be greater than or equal to its final index `j`. If `i < j`, the move is invalid.
- If `start[i] == 'R'`, it must have moved right or stayed put. This implies its starting index `i` must be less than or equal to its final index `j`. If `i > j`, the move is invalid.

We repeat this process until we have scanned both strings. If we successfully match all non-'X' characters without violating any rules, the transformation is possible.

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

        while (i < n || j < n) {
            while (i < n && start.charAt(i) == 'X') {
                i++;
            }
            while (j < n && result.charAt(j) == 'X') {
                j++;
            }

            // If we reached the end of both strings, all non-'X' chars matched.
            if (i == n && j == n) {
                return true;
            }
            
            // If one reached the end but not the other, or chars don't match.
            if (i == n || j == n || start.charAt(i) != result.charAt(j)) {
                return false;
            }

            // Check position constraints
            if (start.charAt(i) == 'L') {
                if (i < j) {
                    return false; // 'L' must move left, so start index must be >= result index
                }
            } else { // Character is 'R'
                if (i > j) {
                    return false; // 'R' must move right, so start index must be <= result index
                }
            }
            
            i++;
            j++;
        }
        
        return true;
    }
}
```
### Algorithm
- Initialize two pointers, `i` for `start` and `j` for `result`, both starting at 0.
- Loop as long as either pointer has not reached the end of its string.
- Inside the loop, advance `i` to the next non-'X' character in `start`.
- Similarly, advance `j` to the next non-'X' character in `result`.
- After finding the next non-'X' characters, perform checks:
  - If one pointer reached the end but the other didn't, the counts of non-'X' characters differ. Return `false`.
  - If both pointers reached the end, all characters have been successfully matched. Return `true`.
  - If `start.charAt(i)` is not equal to `result.charAt(j)`, the relative order is wrong. Return `false`.
  - If the character is 'L', check if `i < j`. If so, an 'L' would have had to move right, which is impossible. Return `false`.
  - If the character is 'R', check if `i > j`. If so, an 'R' would have had to move left, which is impossible. Return `false`.
- If all checks pass for the current pair of characters, increment both `i` and `j` to continue the search.

# Solutions
### Java

```java
class Solution {
public
  boolean canTransform(String start, String end) {
    int n = start.length();
    int i = 0, j = 0;
    while (true) {
      while (i < n && start.charAt(i) == 'X') {
        ++i;
      }
      while (j < n && end.charAt(j) == 'X') {
        ++j;
      }
      if (i == n && j == n) {
        return true;
      }
      if (i == n || j == n || start.charAt(i) != end.charAt(j)) {
        return false;
      }
      if (start.charAt(i) == 'L' && i < j || start.charAt(i) == 'R' && i > j) {
        return false;
      }
      ++i;
      ++j;
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canTransform(string start, string end) {
    int n = start.size();
    int i = 0, j = 0;
    while (true) {
      while (i < n && start[i] == 'X')
        ++i;
      while (j < n && end[j] == 'X')
        ++j;
      if (i == n && j == n)
        return true;
      if (i == n || j == n || start[i] != end[j])
        return false;
      if (start[i] == 'L' && i < j)
        return false;
      if (start[i] == 'R' && i > j)
        return false;
      ++i;
      ++j;
    }
  }
};

```

### Python

```python
class Solution:
    def canTransform(self, start: str, end: str) -> bool: n = len(start) i = j = 0 while 1: while i < n and start[i] == 'X': i += 1 while j < n and end[j] == 'X': j += 1 if i >= n and j >= n: return True if i >= n or j >= n or start[i] != end[j]: return False if start[i] == 'L' and i < j: return False if start[i] == 'R' and i > j: return False i, j = i + 1, j + 1

```