Move Pieces to Obtain a String

medium two pointers string

Problem

You are given two strings start and target of the same length, built only from the characters 'L', 'R', and '_'. A piece 'L' may repeatedly slide one cell to the left when the cell directly left of it is blank, and a piece 'R' may slide one cell to the right into a blank. Pieces can never jump over each other.

Return true if some sequence of such moves can turn start into target, and false otherwise.

Inputstart = "_L__R__R_", target = "L______RR"

Outputtrue

The L slides left from index 1 to 0, the first R slides right from index 4 to 7, and the last R slides right from index 7 to 8.

start (L, R, _ only)

target (same length)

def can_change(start, target):
    n = len(start)
    i = j = 0
    while i < n or j < n:
        while i < n and start[i] == '_':
            i += 1
        while j < n and target[j] == '_':
            j += 1
        if i == n or j == n:
            return i == n and j == n
        if start[i] != target[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 canChange(start, target) {
  const n = start.length;
  let i = 0, j = 0;
  while (i < n || j < n) {
    while (i < n && start[i] === '_') i++;
    while (j < n && target[j] === '_') j++;
    if (i === n || j === n) return i === n && j === n;
    if (start[i] !== target[j]) return false;
    if (start[i] === 'L' && i < j) return false;
    if (start[i] === 'R' && i > j) return false;
    i++; j++;
  }
  return true;
}

boolean canChange(String start, String target) {
    int n = start.length();
    int i = 0, j = 0;
    while (i < n || j < n) {
        while (i < n && start.charAt(i) == '_') i++;
        while (j < n && target.charAt(j) == '_') j++;
        if (i == n || j == n) return i == n && j == n;
        if (start.charAt(i) != target.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 canChange(string start, string target) {
    int n = start.size();
    int i = 0, j = 0;
    while (i < n || j < n) {
        while (i < n && start[i] == '_') i++;
        while (j < n && target[j] == '_') j++;
        if (i == n || j == n) return i == n && j == n;
        if (start[i] != target[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 key observation is that pieces cannot jump over each other, so the left-to-right order of the L and R pieces never changes. If we erase all the blanks, start and target must spell the exact same sequence of L's and R's — otherwise the answer is immediately false.

The second observation is about direction. An L can only slide left, so the k-th piece of start, if it is an L at index i, can only end up at a target index j ≤ i. Symmetrically, an R at index i can only end up at j ≥ i. Blanks impose no other constraint: as long as order and direction are respected, the slides can always be carried out.

That makes a clean two-pointer scan: pointer i walks start and pointer j walks target, each skipping '_' until it lands on a piece. The two pieces must be the same letter; if it is an L we require i ≥ j, and if it is an R we require i ≤ j. Then both pointers advance to hunt for the next pair. If one string runs out of pieces while the other still has one, the counts differ and we return false.

Walking the default example start = "_L__R__R_", target = "L______RR": the first pair is L at i = 1 versus L at j = 0, and 1 ≥ 0 means it can slide left. The next pair is R at i = 4 versus R at j = 7 (4 ≤ 7, slides right), then R at i = 7 versus R at j = 8 (7 ≤ 8). After that both pointers skip the remaining blanks and fall off the end together, so the answer is true.

Each pointer only ever moves forward and each character is inspected at most once per pointer, so the scan is O(n) time. We store nothing but the two indices, giving O(1) extra space.

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