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: trueExplanation: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'`.

# 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.

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`

10x your algorithm interview prep speed. Take the 5-minute quiz: https://algo.monster/evaluator

## More from Algo.Monster

10x your algorithm interview prep speed. Take the 5-minute quiz: https://algo.monster/evaluator