Watch 10 video solutions for Swap Adjacent in LR String, a medium level problem involving Two Pointers, String. This walkthrough by Simple Code - 단순코드 has 4,494 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
In a string composed of 'L', 'R', and 'X' characters, like "RXXLRXRXL", a move consists of either replacing one occurrence of "XL" with "LX", or replacing one occurrence of "RX" with "XR". Given the starting string start and the ending string result, return True if and only if there exists a sequence of moves to transform start to result.
Example 1:
Input: start = "RXXLRXRXL", result = "XRLXXRRLX" Output: true Explanation: We can transform start to result following these steps: RXXLRXRXL -> XRXLRXRXL -> XRLXRXRXL -> XRLXXRRXL -> XRLXXRRLX
Example 2:
Input: start = "X", result = "L" Output: false
Constraints:
1 <= start.length <= 104start.length == result.lengthstart and result will only consist of characters in 'L', 'R', and 'X'.Problem Overview: You get two strings start and end containing 'L', 'R', and 'X'. You may perform swaps XL → LX (L moves left) and RX → XR (R moves right). Determine if start can transform into end. The challenge is validating movement constraints without simulating every swap.
Approach 1: Two Pointer Approach (O(n) time, O(1) space)
Use two pointers to scan both strings while skipping 'X'. The key observation: the relative order of L and R must remain identical after removing X. When both pointers land on a non-X character, compare them. If the characters differ, transformation is impossible. Then enforce movement rules: L can only move left, so its index in start must be greater than or equal to its index in end. R can only move right, so its index in start must be less than or equal to its index in end. Continue scanning until both strings are processed. This linear scan avoids explicit simulation and relies on pointer alignment and movement constraints. This technique is common in two pointers problems involving structural comparisons between sequences.
Approach 2: Index Matching Technique (O(n) time, O(n) space)
Record the indices of L and R characters from both strings while ignoring X. First verify that the sequence of non-X characters is identical; otherwise transformation is impossible. Next compare the index lists. For each L, ensure the index in start is not smaller than the corresponding index in end because L can only move left. For each R, ensure the index in start is not larger than the corresponding index in end because R can only move right. This method separates structure validation from movement validation and is easy to reason about when debugging. It trades constant memory for simpler logic and explicit position tracking using arrays.
Both approaches rely on the same invariant: removing X from both strings must yield the same sequence of characters. The transformation rules only allow directional movement, which creates strict positional constraints for L and R. These properties make the problem a strong exercise in string manipulation and pointer-based scanning.
Recommended for interviews: The Two Pointer Approach. Interviewers expect you to recognize that swaps don't need to be simulated. Demonstrating the ordering invariant and directional constraints shows strong reasoning about string transformations. The index-matching method is also correct, but the constant-space two-pointer scan is typically viewed as the optimal implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointer Approach | O(n) | O(1) | Best general solution. Efficient when comparing two strings while skipping filler characters. |
| Index Matching Technique | O(n) | O(n) | Useful when explicit index tracking improves readability or debugging. |