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

Method 1 - Two-pointer Non-overlapping Scan

Intuition

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.

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).

Complexity

  • ⏰ Time complexity: O(n) – We scan each string once with two pointers.
  • 🧺 Space complexity: O(1) – Only constant extra pointers and counters are used.

Code

 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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

package solution

func canTransform(start string, end string) bool {
    s := []byte(start)
    e := []byte(end)
    n := len(s)
    i, j := 0, 0
    for i < n || j < n {
        for i < n && s[i] == 'X' { i++ }
        for j < n && e[j] == 'X' { j++ }
        if i == n && j == n { return true }
        if i == n || j == n { return false }
        if s[i] != e[j] { return false }
        if s[i] == 'L' && i < j { return false }
        if s[i] == 'R' && i > j { return false }
        i++; j++
    }
    return true
}
 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;
    }
}
 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
    }
}
 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
 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
    }
}
 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;
}