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.
This approach uses two pointers to compare the strings start and result. The main idea is to iterate over both strings and check the movement possibilities for each 'L' and 'R'.
1. Traverse both the start and result strings simultaneously.
2. Skip the 'X' characters because they only represent positions for movement.
3. If characters at the current position are different, or they are not aligned according to the rules 'L' moves left and 'R' moves right, return false.
4. After finishing the iteration, check if both pointers have exhausted the strings.
The function iterates with two pointers over the strings, skipping 'X', and compares the important characters ('L' and 'R'). It validates their relative positions are correct based on movement rules. If the conditions don't hold, it returns false.
The time complexity is O(N) where N is the length of the strings, and the space complexity is O(1) as we are using only a constant amount of extra space.
In this approach, we confirm the transformation using a concept where we compare only the positions of 'L' and 'R', ignoring 'X'.
1. Identify the indices where the characters are 'L' or 'R' in both start and result.
2. Compare the indices:
- Ensure that 'L' in the start can only appear after or at the same position in the result.
- Ensure that 'R' in the start can only appear before or at the same position in the result.
3. If indices mismatch or any conditions above are not met, return false. If everything is as expected, return true.
This C solution extracts the positions of 'L' and 'R' into two parallel arrays, compares them, and finally checks their indices to affirm allowable movements according to problem constraints.
Time complexity is O(N) due to two passes; one for extraction and another for validation. Space complexity is O(N) for arrays tracking positions.
| Approach | Complexity |
|---|---|
| Two Pointer Approach | The time complexity is O(N) where N is the length of the strings, and the space complexity is O(1) as we are using only a constant amount of extra space. |
| Index Matching Technique | Time complexity is O(N) due to two passes; one for extraction and another for validation. Space complexity is O(N) for arrays tracking positions. |
| Default Approach | — |
| 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. |
777. Swap Adjacent in LR String | English | Medium • Simple Code - 단순코드 • 4,494 views views
Watch 9 more video solutions →Practice Swap Adjacent in LR String with our built-in code editor and test cases.
Practice on FleetCode