Swap Adjacent in LR String

We can determine if we can transform the start string into the end string using the given moves by following these insights:

  1. Character Counts: The number of ‘L’ and ‘R’ characters must be the same in both the start and end strings.

  2. Character Positions: The ‘R’ characters in the start string should not move to the left in the end string, and the ‘L’ characters should not move to the right.

With these insights in mind, we can create an algorithm:

  1. Check Lengths: If the lengths of the start and end strings are not the same, return False.

  2. Check Character Counts: If the counts of ‘L’ and ‘R’ in both strings are not the same, return False.

  3. Check Positions: Iterate through the start and end strings simultaneously and compare the positions of ‘L’ and ‘R’.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        # Check if lengths are different
        if len(start) != len(end):
            return False

        # Check if counts of 'L' and 'R' are different
        if start.count('L') != end.count('L') or start.count('R') != end.count('R'):
            return False

        # Compare positions of 'L' and 'R'
        i, j = 0, 0
        while i < len(start) and j < len(end):
            # Skip 'X' characters
            while i < len(start) and start[i] == 'X':
                i += 1
            while j < len(end) and end[j] == 'X':
                j += 1

            # If both strings are fully traversed, return True
            if i == len(start) and j == len(end):
                return True

            # If only one string is fully traversed, or characters are different, return False
            if i == len(start) or j == len(end) or start[i] != end[j]:
                return False

            # Ensure 'L' does not move right and 'R' does not move left
            if (start[i] == 'L' and i < j) or (start[i] == 'R' and i > j):
                return False

            i += 1
            j += 1

        return True

The code returns True if we can transform the start string into the end string using the given moves, otherwise False. It has a time complexity of O(n), where n is the length of the strings, and space complexity is O(1).