Problem statement

https://leetcode.com/problems/swap-adjacent-in-lr-string/

Solution

Actually, quite difficult problem! First, we need to find invariant/half-invariant in this problem:

  1. Number of L, R and X should be the same in both words.
  2. When we delete all X symbols, the order of the rest L and R must be the same.
  3. Moreover, each L letter can be moved only to the left and each R symbol can be moved to the right.

Moreover there 3 conditions not only sufficient but enough! We can see at this string as bunch of people which can be moved only to the left L, only to the right R and vacant places X.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def canTransform(self, start, end):
        if [s for s in start if s != "X"] != [s for s in end if s != "X"]: return False
        
        A = [(s, idx) for idx, s in enumerate(start) if s in "LR"]
        B = [(e, idx) for idx, e in enumerate(end) if e in "LR"]
    
        for (s, i), (e, j) in zip(A, B):
            if s == "L":
                if i < j:
                    return False
            if s == "R":
                if i > j:
                    return False
                
        return True