Skip to main content
Talentd

Swap Adjacent in LR String - Solution & Explanation

MediumTwo PointersString14 min readAsked at: Google, Bloomberg, Lg Electronics
Practice this problem

Problem Statement

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 <= 104
  • start.length == result.length
  • Both start and result will only consist of characters in 'L', 'R', and 'X'.

Approach Overview

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 1: Two Pointer Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Index Matching Technique

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Pointer ApproachO(n)O(1)Best general solution. Efficient when comparing two strings while skipping filler characters.
Index Matching TechniqueO(n)O(n)Useful when explicit index tracking improves readability or debugging.

Video Solution

777. Swap Adjacent in LR String | English | Medium • Simple Code - 단순코드 • 4,618 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Swap Adjacent in LR String easy or hard?
Swap Adjacent in LR String is classified as a Medium problem. The difficulty comes from recognizing that the swap operations impose directional constraints on characters rather than requiring explicit simulation of swaps.
Swap Adjacent in LR String Python/Java solution
Most Python and Java implementations use a two-pointer scan across both strings. Skip 'X' characters, compare the next non-X characters, and check movement constraints for 'L' and 'R'. The logic runs in linear time and requires only constant extra space.
How to solve Swap Adjacent in LR String in O(n)?
Scan both strings with two pointers and skip all 'X' characters. When you encounter 'L' or 'R', ensure the characters match and validate movement constraints: an 'L' index in start must be greater than or equal to its index in end, and an 'R' index must be less than or equal to its index in end. If any constraint fails, transformation is impossible.
What is the best approach for Swap Adjacent in LR String?
The Two Pointer approach is the most efficient and commonly expected solution. Scan both strings while skipping 'X' characters and compare the positions of 'L' and 'R'. Ensure their order is identical and enforce movement rules: 'L' cannot move right and 'R' cannot move left. This runs in O(n) time and O(1) space.
Is Swap Adjacent in LR String asked at Google/Amazon/Meta?
Swap Adjacent in LR String appears in interview preparation sets for companies like Google, Amazon, and Meta. It tests reasoning about string transformations, pointer techniques, and recognizing invariants instead of brute-force simulation.
What data structure is used in Swap Adjacent in LR String?
The optimal solution mainly uses two pointers for sequential scanning. Some implementations also store indices of 'L' and 'R' in arrays or lists to compare positions between the two strings.
What is the time complexity of Swap Adjacent in LR String?
The optimal solution runs in O(n) time where n is the length of the string. Each character is visited at most once using two pointers. Space complexity can be O(1) with the pointer approach or O(n) if storing indices for characters.

Ready to solve this problem?

Practice Swap Adjacent in LR String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Move Pieces to Obtain a String