Problem

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 result, return True if and only if there exists a sequence of moves to transform start to result.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: start = "RXXLRXRXL", result = "XRLXXRRLX"
Output: true
Explanation: We can transform start to result following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Example 2

1
2

Input: start = "X", result = "L"
Output: false

Constraints

  • 1 <= start.length <= 10^4
  • start.length == result.length
  • Both start and result will only consist of characters in 'L', 'R', and 'X'.

Solution

Approach

We use two pointers to scan both strings, skipping ‘X’. For each non-‘X’ character, the order and type must match. ‘L’ can only move left (so its index in start must be >= its index in result), and ‘R’ can only move right (so its index in start must be <= its index in result).

Code

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    bool canTransform(string start, string end) {
        int n = start.size(), 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;
    }
};
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public boolean canTransform(String start, String end) {
        int n = start.length(), 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;
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun canTransform(start: String, end: String): Boolean {
        val n = start.length
        var i = 0; var 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
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        n = len(start)
        i = j = 0
        while i < n or 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 or 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
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn can_transform(start: String, end: String) -> bool {
        let n = start.len();
        let (mut i, mut j) = (0, 0);
        let (s, e) = (start.as_bytes(), end.as_bytes());
        while i < n || j < n {
            while i < n && s[i] == b'X' { i += 1; }
            while j < n && e[j] == b'X' { j += 1; }
            if i == n && j == n { return true; }
            if i == n || j == n { return false; }
            if s[i] != e[j] { return false; }
            if s[i] == b'L' && i < j { return false; }
            if s[i] == b'R' && i > j { return false; }
            i += 1; j += 1;
        }
        true
    }
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

function canTransform(start: string, end: string): boolean {
    const n = start.length;
    let 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;
}

Explanation

We scan both strings, skipping ‘X’. The order and type of ‘L’ and ‘R’ must match, and their allowed movement directions are checked by index. If all checks pass, the transformation is possible.

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)