Generated by Codex with GPT-5

Difficulty: MEDIUM
Problem: Swap Adjacent in LR String

Problem gist

The string contains three characters: L, R, and X. Think of X as an empty space. The only allowed moves are:

1. XL -> LX, which moves an L one position to the left.
2. RX -> XR, which moves an R one position to the right.

Given start and end, the task is to decide whether start can become end after any number of those moves.

The important hidden rule is that L and R never swap with each other. They can only move through X. That means the relative order of the real pieces, after removing every X, must stay exactly the same.

For example, RXXLRXRXL can become XRLXXRRLX. If both strings remove X, they produce the same real-piece sequence: RLRRL. Every R ends at the same index or farther right, and every L ends at the same index or farther left, so the transformation is possible.

Optimal idea

A brute-force simulation is awkward because one piece may move many times, and there can be many possible move orders. The cleaner solution is to ignore the move sequence and check whether the final arrangement obeys the movement constraints.

There are two checks:

First, remove all X characters from both strings. The remaining sequence of L and R must match. If it does not, some real piece would have to cross another real piece, which is impossible because the operations only swap a real piece with X.

Second, compare each matching real piece by its position in start and end:

1. An L can only move left, so its start index must be greater than or equal to its end index.
2. An R can only move right, so its start index must be less than or equal to its end index.

If both checks pass for every real piece, the transformation is possible. This gives O(n) time because each string is scanned once, and O(1) extra working space if the real pieces are streamed instead of copied into lists.

How to derive it

Start by translating the two operations into motion:

XL -> LX means the L moved left across one empty slot. There is no rule that moves L right.

RX -> XR means the R moved right across one empty slot. There is no rule that moves R left.

That explains the direction constraints, but direction alone is not enough. The other key observation is that neither operation contains LR -> RL or RL -> LR. A real piece can slide through empty slots, but two real pieces cannot pass each other. So if the real-piece sequence changes after removing X, the answer must be false immediately.

Once those two facts are clear, there is no need to search through moves. Pair the first real piece in start with the first real piece in end, the second with the second, and so on. Each pair must have the same letter and must move in an allowed direction. If every pair passes, the empty slots can absorb the step-by-step swaps needed to slide each piece into place.

Python solution

from itertools import zip_longest
from typing import Iterator, Tuple


Piece = Tuple[int, str]


class LRStringTransformer:
    """Validate whether one LR string can transform into another."""

    EMPTY_SLOT = "X"

    def can_transform(self, start: str, end: str) -> bool:
        if len(start) != len(end):
            return False

        for start_piece, end_piece in zip_longest(
            self._real_pieces(start),
            self._real_pieces(end),
        ):
            if start_piece is None or end_piece is None:
                return False

            start_index, start_label = start_piece
            end_index, end_label = end_piece

            if start_label != end_label:
                return False

            if not self._can_piece_reach(start_label, start_index, end_index):
                return False

        return True

    def _real_pieces(self, state: str) -> Iterator[Piece]:
        for index, label in enumerate(state):
            if label != self.EMPTY_SLOT:
                yield index, label

    def _can_piece_reach(
        self,
        label: str,
        start_index: int,
        end_index: int,
    ) -> bool:
        # L moves left by repeatedly applying XL -> LX.
        if label == "L":
            return start_index >= end_index

        # R moves right by repeatedly applying RX -> XR.
        if label == "R":
            return start_index <= end_index

        return False


class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        return LRStringTransformer().can_transform(start, end)

Why this works

The generator _real_pieces yields every non-X character with its original index. Pairing these generated streams compares real pieces in their left-to-right order. If one stream ends earlier, or if the paired labels differ, then start and end have different real-piece sequences. That cannot be fixed by legal moves because legal moves never swap two real pieces.

After the order check passes, each paired piece represents the same physical L or R. An L can only move left across empty slots, so it cannot finish at a larger index than where it started. An R can only move right across empty slots, so it cannot finish at a smaller index than where it started. The helper _can_piece_reach encodes exactly those two constraints.

If every real piece has the same relative order and moves only in its legal direction, the required empty slots are available along the way because all missing positions are X. The transformation can be realized by sliding pieces through those slots without any real piece crossing another.

The runtime is O(n) for strings of length n. The extra working space is O(1) beyond the generator state because the code does not build stripped copies of the strings.

Interview follow-ups

What if the interviewer asks for the actual move sequence?

The feasibility check above should still be the first step. If it fails, no sequence exists. If it passes, one practical construction is to move L pieces from left to right into their target positions, then move R pieces from right to left into their target positions, using adjacent swaps with X.

That order avoids accidentally moving a piece through another real piece. Each individual swap preserves the same invariants used by the validator: L only moves left, R only moves right, and the real-piece order never changes. The tradeoff is output size. A valid sequence can require many adjacent swaps, so producing the moves may take O(k) time and space where k is the number of swaps, which can be O(n^2) in the worst case.

What if both movement directions are allowed?

If L and R could each move both left and right through X, the direction checks would disappear. The only remaining invariant would be the order of real pieces after removing X. As long as the non-X sequences match, the pieces can slide through empty slots to reach the target positions without crossing each other.

The expected solution would scan both strings and compare their non-X streams. That keeps the same O(n) time and can still use O(1) extra working space with generators or two pointers. The problem becomes easier because individual positions no longer constrain feasibility.

What if the interviewer adds another piece type with its own movement rule?

The same framework generalizes well. First compare the sequence of all non-empty pieces, because no real pieces can cross unless the new rules explicitly allow crossing. Then apply a per-piece reachability rule based on the movement direction of that piece.

For example, a piece that only moves left uses start_index >= end_index, a piece that only moves right uses start_index <= end_index, and a piece that moves both ways accepts any index. The complexity remains O(n) if each piece has a constant-time reachability check. The tradeoff is that the correctness proof must be revisited if any new operation lets two real pieces swap places, because then the preserved-order invariant would no longer hold.

What if there are many queries against the same strings?

For isolated LeetCode calls, a single linear scan is optimal and simplest. For many repeated queries, it can be useful to preprocess each string into its real-piece signature: the sequence of labels and their indices. Then each query compares signatures and direction constraints over those compact arrays.

Preprocessing one string costs O(n) time and O(m) space, where m is the number of real pieces. Each comparison then costs O(m) instead of scanning all n characters. This helps when strings are long and mostly X, or when the same states are reused many times. It is not worth the extra storage for the standard one-shot problem.

Why is counting characters not enough?

Having the same number of L, R, and X characters is necessary but much too weak. For example, LRX and RLX have identical counts, but they are not transformable because the L and R would need to cross each other.

The expected explanation is that this is an ordering problem, not just a counting problem. Counts can prove that a transformation is impossible when totals differ, but they cannot prove possibility. The real invariant is the full non-X sequence plus the direction constraint for each piece. Checking those still takes only O(n) time, so there is no reason to settle for the weaker count-only test.

Takeaway

The problem becomes simple once the moves are treated as invariants rather than as a search tree. Legal swaps preserve the order of real pieces. They also let L move only left and R move only right. Comparing the non-X streams and checking those index directions gives a direct, optimal O(n) solution.