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'.In #777 Swap Adjacent in LR String, the goal is to determine whether one string can be transformed into another using only the swaps "XL" → "LX" and "RX" → "XR". These rules imply that L can only move left and R can only move right. A key observation is that the relative order of the characters L and R must remain the same when all X characters are ignored.
An efficient strategy uses the two pointers technique. Traverse both strings while skipping X. When matching non-X characters are found, verify movement constraints: L cannot move to the right of its original position and R cannot move to the left. If any constraint is violated, the transformation is impossible.
This approach works in a single pass through both strings and avoids extra data structures, making it highly efficient for interview settings.
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers with X Skipping | O(n) | O(1) |
| Filtered String Comparison + Validation | O(n) | O(n) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Think of the L and R's as people on a horizontal line, where X is a space. The people can't cross each other, and also you can't go from XRX to RXX.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or similar transformation-based string questions appear in technical interviews at major companies. It tests understanding of constraints, pointer techniques, and reasoning about string transformations.
The optimal approach uses a two-pointer traversal while skipping 'X' characters. By comparing the positions of 'L' and 'R' in both strings and enforcing their movement constraints, we can validate the transformation in linear time.
No complex data structure is required. A simple two-pointer technique on the two strings is sufficient, making the solution efficient in both time and space.
The allowed swaps only move characters across 'X' but never allow 'L' and 'R' to cross each other. Therefore, if you remove all 'X' characters, the remaining sequence of 'L' and 'R' must be identical in both strings.