Swap Adjacent in LR String

medium two-pointers strings invariants

Problem

Strings consist of 'L', 'R', 'X'. Moves are XL -> LX and RX -> XR. Decide whether start can be transformed into end.

Inputstart='RXXLRXRXL', end='XRLXXRRLX'

Outputtrue

A valid sequence of moves exists.

start & end (L, R, X)

def canTransform(start, end):
    if start.replace('X','') != end.replace('X',''):
        return False
    i = j = 0
    n = len(start)
    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 or j == n: return i == j == n
        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

function canTransform(start, end) {
  if (start.replace(/X/g, '') !== end.replace(/X/g, '')) return false;
  let i = 0, j = 0, n = start.length;
  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 i === n && j === n;
    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;
}

boolean canTransform(String start, String end) {
    if (!start.replace("X","").equals(end.replace("X",""))) return false;
    int i = 0, j = 0, n = start.length();
    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 i == n && j == n;
        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;
}

bool canTransform(string start, string end) {
    string a, b;
    for (char c : start) if (c != 'X') a += c;
    for (char c : end) if (c != 'X') b += c;
    if (a != b) return false;
    int i = 0, j = 0, n = start.size();
    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 i == n && j == n;
        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

The moves are XL → LX and RX → XR. Read carefully: each move only slides an L one step to the left, or an R one step to the right. The X's are just empty space. So instead of simulating moves, we check two simple rules.

Rule 1 — same letters in the same order. Since L and R can never swap past each other and never change into something else, removing every X from start and from end must give the identical string. The code checks start.replace('X','') != end.replace('X','') first and returns false if they differ.

Rule 2 — each letter is reachable. We walk two pointers i over start and j over end, skipping X's so they land on real letters. The matched letters must agree. An L can only move left, so in start it must sit at index i ≥ j; if i < j it would have to move right, which is illegal. An R can only move right, so it needs i ≤ j; if i > j that fails.

Example: start='RXXLRXRXL', end='XRLXXRRLX'. Stripped, both are RLRRL, so Rule 1 passes. Then each R only ever needs to slide right and each L left, so Rule 2 holds and the answer is true.

Because we look at each character a constant number of times, the whole check is one linear scan.

Time: O(n) Space: O(n)