# LeetCode 777. Swap Adjacent in LR String. Google Interview 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 1:**

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

**Output:** true

**Explanation:**

We can transform start to end following these steps:

RXXLRXRXL ->

XRXLRXRXL ->

XRLXRXRXL ->

XRLXXRRXL ->

XRLXXRRLX

**Example 2:**

**Input:** start = "LLR", end = "RRL"

**Output:** false

**Example 3:**

**Input:** start = "XLLR", end = "LXLX"

**Output:** false

**Constraints:**

`1 <= start.length <= 104`

`start.length == end.length`

- Both
`start`

and`end`

will only consist of characters in`'L'`

,`'R'`

, and`'X'`

.

This question was recently asked by Google for virtual onsite interviews.

# Explanation

Key observations:

There are three kinds of characters, ‘L’, ‘R’, ‘X’.

Replacing `XL`

with `LX`

= move `L`

to the left by one

Replacing `RX`

with `XR`

= move `R`

to the right by one

If we remove all the `X`

in both strings, the resulting strings should be the same.

Additional observations:

Since a move always involves `X`

, an `L`

or `R`

cannot move through another `L`

or `R`

.

Since an`L`

can only move to the right, for each occurrence of `L`

in the start string, its position should be to the same or to the left of its corresponding `L`

in the end string.

And vice versa for the `R`

characters.

**Implementation**

We first compare two strings with X removed. This checks relative position between Ls and Rs are correct.

Then we find the indices for each occurence of L and check the condition in the above figure. Then we do the same for R.

class Solution:

def canTransform(self, start: str, end: str) -> bool:

if len(start) != len(end): return False

# check L R orders are the same

if start.replace('X','') != end.replace('X', ''): return False

n = len(start)

Lstart = [i for i in range(n) if start[i] == 'L']

Lend = [i for i in range(n) if end[i] == 'L']

Rstart = [i for i in range(n) if start[i] == 'R']

Rend = [i for i in range(n) if end[i] == 'R']# check L positions are correct

for i, j in zip(Lstart, Lend):

if i < j:

return False

# check R positions are correct

for i, j in zip(Rstart, Rend):

if i > j:

return False

return True