> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/777-swap-adjacent-in-lr-string.md).

# 777 Swap Adjacent in LR String

## 777. [Swap Adjacent in LR String](https://leetcode.com/problems/swap-adjacent-in-lr-string/description/)

## 1. Question

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`end`, return`True`if and only if there exists a sequence of moves to transform one string to the other.

**Example:**

```
Input: start = "RXXLRXRXL", end = "XRLXXRRLX"

Output: True

Explanation:
We can transform start to end following these steps:
RXXLRXRXL -> 
XRXLRXRXL ->
XRLXRXRXL -> 
XRLXXRRXL -> 
XRLXXRRLX
```

**Note:**

1. `1 <= len(start) = len(end) <= 10000`.
2. Both start and end will only consist of characters in`{'L', 'R', 'X'}`.

## 2. Implementation

**(1) Two Pointers**

```java
class Solution {
    public boolean canTransform(String start, String end) {
        if (start.length() != end.length()) {
            return false;
        } 

        int countX1 = 0, countX2 = 0;
        int index1 = 0, index2 = 0;

        while (index1 < start.length() && index2 < end.length()) {
            // Get the first non x character in start string, and count the number of X 
            while (index1 < start.length() && start.charAt(index1) == 'X') {
                ++countX1;
                ++index1;
            }

            // Get the first non x character in end string, and count the number of X
            while (index2 < end.length() && end.charAt(index2) == 'X') {
                ++countX2;
                ++index2;
            }

            // Both strings get to the end, return true;
            if (index1 == start.length() && index2 == end.length()) {
                return true;
            }
            // One of the string is running out of character, return false;
            else if (index1 == start.length() || index2 == end.length()) {
                return false;
            }
            // If the first non x character are different, since L will only get to left, and R can only get to right,
            // there is no way for start string to be transformed into end string
            else if (start.charAt(index1) != end.charAt(index2)) {
                return false;
            }
            // L can only get to left, if number of x in start is less than number of x in end string, it is impossible for e
            // start string to be transformed into end string
            else if (start.charAt(index1) == 'L' && countX1 < countX2) {
                return false;
            }
            // R can only get tor right, if number of x in start is greater than the number of x in end string, it is impossible 
            // start string to be transformed into end string
            else if (start.charAt(index1) == 'R' && countX1 > countX2) {
                return false;
            }
            else {
                ++index1;
                ++index2;
            }
        }
        return true;
    }
}
```

## 3. Time & Space Complexity

**Two Pointers:** 时间复杂度O(n), 空间复杂度O(1)