Code Implementation

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        if start.replace('X', '') != end.replace('X', ''):
            return False

        n = len(start)
        i = j = 0
        while i < n and j < n:
            while i < n and start[i] == 'X':
                i += 1
            while j < n and end[j] == 'X':
                j += 1
            if i == n and j == n:
                return True
            if (i == n) != (j == n):
                return False
            if start[i] != end[j]:
                return False
            if start[i] == 'L' and i < j:
                return False
            if start[i] == 'R' and i > j:
                return False
            i += 1
            j += 1
        return True
      

class Solution {
public:
    bool canTransform(string start, string end) {
        string s1, s2;
        for (char c : start) if (c != 'X') s1 += c;
        for (char c : end) if (c != 'X') s2 += c;
        if (s1 != s2) return false;

        int n = start.size();
        int i = 0, j = 0;
        while (i < n && j < n) {
            while (i < n && start[i] == 'X') i++;
            while (j < n && end[j] == 'X') j++;
            if (i == n && j == n) return true;
            if ((i == n) != (j == n)) return false;
            if (start[i] != end[j]) return false;
            if (start[i] == 'L' && i < j) return false;
            if (start[i] == 'R' && i > j) return false;
            i++;
            j++;
        }
        return true;
    }
};
      

class Solution {
    public boolean canTransform(String start, String end) {
        if (!start.replace("X", "").equals(end.replace("X", ""))) {
            return false;
        }
        int n = start.length();
        int i = 0, j = 0;
        while (i < n && j < n) {
            while (i < n && start.charAt(i) == 'X') i++;
            while (j < n && end.charAt(j) == 'X') j++;
            if (i == n && j == n) return true;
            if ((i == n) != (j == n)) return false;
            if (start.charAt(i) != end.charAt(j)) return false;
            if (start.charAt(i) == 'L' && i < j) return false;
            if (start.charAt(i) == 'R' && i > j) return false;
            i++;
            j++;
        }
        return true;
    }
}
      

var canTransform = function(start, end) {
    if (start.replace(/X/g, '') !== end.replace(/X/g, '')) {
        return false;
    }
    let n = start.length, i = 0, j = 0;
    while (i < n && j < n) {
        while (i < n && start[i] === 'X') i++;
        while (j < n && end[j] === 'X') j++;
        if (i === n && j === n) return true;
        if ((i === n) !== (j === n)) return false;
        if (start[i] !== end[j]) return false;
        if (start[i] === 'L' && i < j) return false;
        if (start[i] === 'R' && i > j) return false;
        i++;
        j++;
    }
    return true;
};
      

Problem Description

You are given two strings, start and end, both consisting only of the characters 'L', 'R', and 'X'. You can perform the following operation any number of times:

• Choose two adjacent characters in start and swap them, but only if the swap is either "XL" → "LX" or "RX" → "XR".

Return true if and only if you can transform start into end using any sequence of these allowed swaps.

Key constraints:

• Each character in start and end is either 'L', 'R', or 'X'.
• Swaps can only move 'L' to the left and 'R' to the right by swapping with 'X'.
• All swaps are local (adjacent characters only).
• The relative order of 'L' and 'R' must be preserved (cannot "jump over" each other).

Thought Process

At first glance, it may seem that we have to simulate all possible swaps to check if start can be transformed into end. However, this would be inefficient, especially for long strings. Instead, let's analyze the movement rules:

• 'L' can only move left by swapping with an 'X' on its left ("XL" → "LX").
• 'R' can only move right by swapping with an 'X' on its right ("RX" → "XR").
• 'L' can never move right, and 'R' can never move left.
• 'L' and 'R' cannot cross each other.

These constraints suggest that the order and types of 'L' and 'R' must stay the same, and only their positions relative to 'X' can change. This insight allows us to avoid brute-force simulation.

Solution Approach

• Step 1: Check Non-X Order
  Remove all 'X' characters from both start and end. If the resulting strings are not identical, it is impossible to transform start into end. This is because 'L' and 'R' cannot cross or change order.
• Step 2: Compare Movements
  Use two pointers, one for start and one for end. For every non-'X' character:
  • If the character is 'L', its position in start must be the same or to the right of its position in end (since 'L' can only move left).
  • If the character is 'R', its position in start must be the same or to the left of its position in end (since 'R' can only move right).
• Step 3: Pointer Iteration
  Iterate through both strings, skipping 'X' characters, and compare the positions and types as described above.
• Step 4: Edge Cases
  If one pointer reaches the end before the other, or if any of the above checks fail, return false.

This approach ensures that all movement and order constraints are respected, and runs in linear time.

Example Walkthrough

Example:
start = "RXXLRXRXL"
end = "XRLXXRRLX"

1. Remove all 'X':
   • start without 'X': RLRRL
   • end without 'X': RLRRL
   They match, so continue.
2. Use two pointers to compare positions:
   • First 'R' in start at index 0, in end at index 1. Since 'R' can only move right, 0 <= 1, OK.
   • First 'L' in start at index 3, in end at index 2. Since 'L' can only move left, 3 >= 2, OK.
   • Continue this way for all non-'X' characters.
3. All checks pass; return true.

At each step, we ensure 'L' doesn't move right and 'R' doesn't move left, and the order is preserved.

Time and Space Complexity

• Brute-force simulation: Would require exploring all possible swaps, leading to exponential time complexity, which is infeasible for large strings.
• Optimized approach:
  • Time Complexity: O(n), where n is the length of the strings. We scan through both strings only once.
  • Space Complexity: O(1) extra space (ignoring the space for the input strings), or O(n) if you count the temporary strings created when removing 'X'.

Summary

The key insight is that 'L' and 'R' cannot cross each other or move in the wrong direction, and their order must be preserved. By reducing the problem to comparing the positions of non-'X' characters and using two pointers, we achieve an efficient and elegant solution that checks all constraints in linear time.