# Leetcode: Swap Adjacent in LR String Similar Problems:

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’}.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/swap-adjacent-in-lr-string
## Basic Ideas: Check 3 rules
##       R won't bypass X: count 'R' from left to right
##       X won't bypass L: count 'L' from right to left
##       R won't bypass L: remove 'X', then confirm two strings equal
##
## Complexity: Time O(n), Space O(1)
class Solution:
def canTransform(self, start, end):
"""
:type start: str
:type end: str
:rtype: bool
"""
if start.count('X') != end.count('X') or \
start.count('L') != end.count('L') or \
start.count('R') != end.count('R'):
return False

## Pass1: from left to right, 'R' count in start should be no smaller than end string
count1, count2 = 0, 0
for i in range(0, len(start)):
if start[i] == 'R': count1 += 1
if end[i] == 'R': count2 += 1
if count1<count2: return False

## Pass2: from right to left, 'L' count in start should be no smaller than end string
count1, count2 = 0, 0
for i in range(len(start)-1, -1, -1):
if start[i] == 'L': count1 += 1
if end[i] == 'L': count2 += 1
if count1<count2: return False

# check3: remove X, then the two shall equal
return start.replace('X', '') == end.replace('X', '')
```

Share It, If You Like It.