# 777. Swap Adjacent in LR String

ref:

{% embed url="https://leetcode.com/problems/swap-adjacent-in-lr-string/discuss/217070/Python-using-corresponding-position-" %}

ref:&#x20;

[https://www.cnblogs.com/grandyang/p/9001474.html](https://www.cnblogs.com/grandyang/p/9001474.html)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FgJYGSt2FBoCnvr76jkO3%2Fimage.png?alt=media\&token=15ca9111-a327-4c29-a141-4a83034306b1)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FIdH9uN06ibgwWMamU7Ht%2Fimage.png?alt=media\&token=d79e930d-131e-42e0-984a-3a0d8f09d666)

## two pointers

```
T: O(n)
S: O(1)
```

```java
class Solution {
    public boolean canTransform(String start, String end) {
         // remove X, start and end should the same
        if (!start.replace("X", "").equals(end.replace("X", ""))) {
            return false;
        }
        
        int n = start.length();
        int sIdx = 0;
        int eIdx = 0;
        while (sIdx < n && eIdx < n) {
            // 遇到 'X' 略過
            while (sIdx < n && start.charAt(sIdx) == 'X') {
                sIdx++;
            }
            while (eIdx < n && end.charAt(eIdx) == 'X') {
                eIdx++;
            }

            // 可能前面 while 最後跳出時剛好在 n
            if (sIdx == n && eIdx == n) { //代表跑完了
                return true;
            }
            if (sIdx == n || eIdx == n) { //一長一短, 一定錯
                return false;
            }
            
            char s = start.charAt(sIdx);
            char e = end.charAt(eIdx); 
            if (s != e) { // 照理去掉 X 後, start end 指向同一個字
                return false;
            }
            if (s == 'L' && eIdx > sIdx) { // check 位置, Ｌ eidx 應該會越來越小
                return false;
            }
            if (s == 'R' && eIdx < sIdx) { // check 位置, Ｌ eidx 應該會越來越大
                return false;
            }
            
            sIdx++;
            eIdx++;
        }
        return true;
        
    }
    
}

/*
1.
"XL" with "LX", or replacing one occurrence of 
"RX" with "XR"

"XL" with "LX" => we can get L will continuously move to left
"RX" with "XR" => we can get R will continuously move to right

2.
so in correct case, after swaping, R shoud in right side (end index > start index)
RXXLRXRXL (start index: 0)
p
XRLXXRRLX (end index: 1)
 p
and after change, the start[start index] == end[end index] => start[0] == end[1] == R

3.
so in correct case, after swaping, L shoud in left side (end index < start index)
RXXLRXRXL (start index: 3)
   p
XRLXXRRLX (end index: 2)
  p

and after change, the start[start index] == end[end index] => start[3] == end[2] == L
 
4.
one more noticed!
remove X, they should the same
"RXXLRXRXL" => RLRRL
"XRLXXRRLX" => RLRRL
一開始的判斷
if (!start.replace("X", "").equals(end.replace("X", ""))) {
    return false;



T: O(n)
S: O(1)
*/
```
