LeetCode 777. Swap Adjacent in LR String. Google Interview Question.
In a string composed of
'X' characters, like
"RXXLRXRXL", a move consists of either replacing one occurrence of
"LX", or replacing one occurrence of
"XR". Given the starting string
start and the ending string
True if and only if there exists a sequence of moves to transform one string to the other.
Input: start = "RXXLRXRXL", end = "XRLXXRRLX"
We can transform start to end following these steps:
Input: start = "LLR", end = "RRL"
Input: start = "XLLR", end = "LXLX"
1 <= start.length <= 104
start.length == end.length
endwill only consist of characters in
This question was recently asked by Google for virtual onsite interviews.
There are three kinds of characters, ‘L’, ‘R’, ‘X’.
LX = move
L to the left by one
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
R cannot move through another
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
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.
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:
# check R positions are correct
for i, j in zip(Rstart, Rend):
if i > j: