What is the two-pointer scanning approach in the 'Swap Adjacent in LR String' problem?

The two-pointer scanning approach involves using two pointers to traverse the start and result strings simultaneously, ensuring that 'L' and 'R' characters are swapped according to the allowed operations without violating their movement constraints.

How can I solve the 'Swap Adjacent in LR String' problem efficiently?

To solve the problem efficiently, use two-pointer scanning with invariant tracking. This ensures a linear time solution with O(n) time complexity, where n is the length of the string.

Can the solution to this problem be done in constant space?

Yes, the solution can be done in constant space, as you only need a few variables to maintain the positions of the pointers and track character movement without using extra data structures.

How does the invariant tracking work in this problem?

Invariant tracking involves ensuring that the relative order of 'L' and 'R' characters remains consistent as you traverse both strings. The character movements must not violate the problem's transformation rules.

What are some common pitfalls in solving the 'Swap Adjacent in LR String' problem?

Common pitfalls include misunderstanding the invariant constraint, failing to handle edge cases like unequal numbers of 'L' and 'R' characters, or overcomplicating the solution with unnecessary complexity.

#777

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

在 LR 字符串中交换相邻字符

在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如 "RXXLRXRXL" ）中进行移动操作。一次移动操作指用一个 "LX" 替换一个 "XL" ，或者用一个 "XR" 替换一个 "RX" 。现给定起始字符串 start 和结束字符串 result ，请编写代码，当且仅当存在一系列…

双指针字符串

题目描述

在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个 "LX" 替换一个 "XL"，或者用一个 "XR" 替换一个 "RX"。现给定起始字符串 start 和结束字符串 result，请编写代码，当且仅当存在一系列移动操作使得 start 可以转换成 result 时，返回 True。

示例 1：

输入：start = "RXXLRXRXL", result = "XRLXXRRLX"
输出：true
解释：通过以下步骤我们可以将 start 转化为 result：
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

示例 2：

输入：start = "X", result = "L"
输出：false

提示：

1 <= start.length <= 10⁴
start.length == result.length
start 和 result 都只包含 'L', 'R' 或 'X'。

lightbulb

解题思路

方法一：双指针

替换操作实际上是将 L 往左移动（L 左边为 X 时才能移动），R 往右移动（R 右边是 X 时才能移动），但 L 无法穿过 R。所以，如果去掉 start 和 end 中的所有 X，剩下的字符应该是相同的，否则返回 false。

双指针遍历 start 和 end：

如果当前字符为 L 且 $i\lt j$ ，那么这个 L 无法向右移动，返回 false；
如果当前字符为 R 且 $i\gt j$ ，那么这个 R 无法向左移动，返回 false。

如果双指针均遍历到末尾，返回 true。

时间复杂度 $O(n)$ ，其中 $n$ 表示字符串 start 或 end 的长度。

相似题目：

2337. 移动片段得到字符串

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        n = len(start)
        i = j = 0
        while 1:
            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 or 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, j = i + 1, j + 1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Test for edge cases where the start and result strings are identical or very small.
question_mark
Look for solutions that efficiently handle large inputs within the constraints.
question_mark
Evaluate if the candidate can explain the importance of character invariants in the two-pointer approach.

warning

常见陷阱

外企场景

error
Misunderstanding the invariant constraint, leading to incorrect swapping logic.
error
Failing to handle edge cases like strings with only 'X' characters or strings with an unequal number of 'L' and 'R' characters.
error
Overcomplicating the solution by not recognizing that the problem can be solved with linear time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider a variant where the transformation allows more than two types of operations, introducing additional constraints.
arrow_right_alt
Modify the problem by requiring that no two 'L' characters are allowed to swap positions with each other.
arrow_right_alt
Introduce a constraint that limits the number of swaps that can be performed in each transformation, testing the efficiency of the algorithm.

help

常见问题

外企场景

继续练习

#763 划分字母区间 #809 情感丰富的文字 #821 字符的最短距离