[LeetCode] 777. Swap Adjacent in LR String

Medium · Two Pointers · O(n) time / O(1) space

문제

'L', 'R', 'X'로 이루어진 문자열에서 다음 두 이동만 허용된다.

• XL → LX (L이 왼쪽으로 한 칸)
• RX → XR (R이 오른쪽으로 한 칸)

start를 이동들의 시퀀스로 result로 만들 수 있는지 판별한다.

핵심 관찰

두 규칙 모두 L/R이 X하고만 자리를 바꾼다. LR → RL 같은 변환은 없으므로 L과 R은 서로를 절대 넘을 수 없다. 여기서 두 가지 불변량이 나온다.

1. 뼈대 불변: X를 전부 지운 서브시퀀스는 어떤 이동으로도 변하지 않는다.

   RXXLRXRXL → RLRRL
   XRLXXRRLX → RLRRL   (같아야 변환 가능)

2. 방향 제약: L은 왼쪽으로만 이동하므로 start에서의 인덱스 ≥ result에서의 인덱스여야 하고, R은 그 반대다.

뼈대가 같고 각 문자가 방향 제약을 만족하면, 각 L/R을 X 위로 독립적으로 밀어 목표 위치에 보낼 수 있으므로 충분조건이기도 하다.

풀이

function canTransform(start: string, result: string): boolean {
  const n = start.length
  let i = 0
  let j = 0
  while (i < n || j < n) {
    while (i < n && start[i] === 'X') i++
    while (j < n && result[j] === 'X') j++
    if (start[i] !== result[j]) return false      // 뼈대 불일치
    if (start[i] === 'L' && i < j) return false   // L은 왼쪽으로만
    if (start[i] === 'R' && i > j) return false   // R은 오른쪽으로만
    i++
    j++
  }
  return true
}

두 포인터 i, j가 각 문자열의 "k번째 non-X 문자"를 짝지어 비교한다.

• 문자가 다르면 뼈대 불일치로 즉시 false
• L인데 i < j면 L이 오른쪽으로 가야 하므로 false
• R인데 i > j면 R이 왼쪽으로 가야 하므로 false

한쪽만 먼저 끝에 도달한 경우(non-X 개수가 다른 경우)는 start[i]가 undefined가 되어 첫 번째 비교(undefined !== 'L')에서 자연스럽게 false로 걸러진다.

복잡도

• 시간: O(n), 각 포인터가 문자열을 한 번씩만 순회
• 공간: O(1)