777. Swap Adjacent in LR String - Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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 <= 10⁴
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.

Python

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        i, j = 0, 0
        n = len(start)
        while i < n and j < n:
            while i < n and start[i] == 'X':
                i += 1
            while j < n and end[j] == 'X':
                j += 1
            if i < n and j < n:
                if 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 += 1
                j += 1
        while i < n and start[i] == 'X':
            i += 1
        while j < n and end[j] == 'X':
            j += 1
        return i == j

Java

public class Solution {
    public boolean canTransform(String start, String end) {
        int i = 0, j = 0;
        int n = start.length();
        while (i < n && j < n) {
            while (i < n && start.charAt(i) == 'X') i++;
            while (j < n && end.charAt(j) == 'X') j++;
            if (i < n && j < n) {
                if (start.charAt(i) != end.charAt(j)) return false;
                if (start.charAt(i) == 'L' && i < j) return false;
                if (start.charAt(i) == 'R' && i > j) return false;
                i++; j++;
            }
        }
        while (i < n && start.charAt(i) == 'X') i++;
        while (j < n && end.charAt(j) == 'X') j++;
        return i == j;
    }
}

C++

#include <string>
using namespace std;

class Solution {
public:
    bool canTransform(string start, string end) {
        int i = 0, j = 0, n = start.size();
        while (i < n && j < n) {
            while (i < n && start[i] == 'X') i++;
            while (j < n && end[j] == 'X') j++;
            if (i < n && j < n) {
                if (start[i] != end[j]) return false;
                if (start[i] == 'L' && i < j) return false;
                if (start[i] == 'R' && i > j) return false;
                i++; j++;
            }
        }
        while (i < n && start[i] == 'X') i++;
        while (j < n && end[j] == 'X') j++;
        return i == j;
    }
};

JavaScript

function canTransform(start, end) {
    let i = 0, j = 0;
    const n = start.length;
    while (i < n && j < n) {
        while (i < n && start[i] === 'X') i++;
        while (j < n && end[j] === 'X') j++;
        if (i < n && j < n) {
            if (start[i] !== end[j]) return false;
            if (start[i] === 'L' && i < j) return false;
            if (start[i] === 'R' && i > j) return false;
            i++; j++;
        }
    }
    while (i < n && start[i] === 'X') i++;
    while (j < n && end[j] === 'X') j++;
    return i === j;
}

#include <stdbool.h>
#include <string.h>

bool canTransform(char *start, char *end) {
    int i = 0, j = 0;
    int len = strlen(start);
    while (i < len && j < len) {
        while (i < len && start[i] == 'X') i++;
        while (j < len && end[j] == 'X') j++;
        if (i < len && j < len) {
            if (start[i] != end[j]) return false;
            if (start[i] == 'L' && i < j) return false;
            if (start[i] == 'R' && i > j) return false;
            i++; j++;
        }
    }
    while (i < len && start[i] == 'X') i++;
    while (j < len && end[j] == 'X') j++;
    return i == j;
}

public class Solution {
    public bool CanTransform(string start, string end) {
        int i = 0, j = 0, n = start.Length;
        while (i < n && j < n) {
            while (i < n && start[i] == 'X') i++;
            while (j < n && end[j] == 'X') j++;
            if (i < n && j < n) {
                if (start[i] != end[j]) return false;
                if (start[i] == 'L' && i < j) return false;
                if (start[i] == 'R' && i > j) return false;
                i++; j++;
            }
        }
        while (i < n && start[i] == 'X') i++;
        while (j < n && end[j] == 'X') j++;
        return i == j;
    }
}

This Python code efficiently uses two pointers (i and j) to check non-'X' characters for equality and permissible movement, covered in a loop that terminates once a mismatch or improper movement is found.

Complexity

With a time complexity of O(N) based on the linear traversal and constant space complexity O(1).

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.

Python

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        sidx = [i for i, x in enumerate(start) if x != 'X']
        eidx = [i for i, x in enumerate(end) if x != 'X']
        if len(sidx) != len(eidx):
            return False
        for si, ei in zip(sidx, eidx):
            if start[si] != end[ei]:
                return False
            if start[si] == 'L' and si < ei:
                return False
            if start[si] == 'R' and si > ei:
                return False
        return True

Java

import java.util.*;

public class Solution {
    public boolean canTransform(String start, String end) {
        List<Integer> sidx = new ArrayList<>(), eidx = new ArrayList<>();
        int n = start.length();
        for (int i = 0; i < n; i++) {
            if (start.charAt(i) != 'X') sidx.add(i);
            if (end.charAt(i) != 'X') eidx.add(i);
        }
        if (sidx.size() != eidx.size()) return false;
        for (int i = 0; i < sidx.size(); i++) {
            if (start.charAt(sidx.get(i)) != end.charAt(eidx.get(i))) return false;
            if (start.charAt(sidx.get(i)) == 'L' && sidx.get(i) < eidx.get(i)) return false;
            if (start.charAt(sidx.get(i)) == 'R' && sidx.get(i) > eidx.get(i)) return false;
        }
        return true;
    }
}

C++

#include <string>
using namespace std;

class Solution {
public:
    bool canTransform(string start, string end) {
        vector<int> sidx, eidx;
        int n = start.size();
        for (int i = 0; i < n; i++) {
            if (start[i] != 'X') sidx.push_back(i);
            if (end[i] != 'X') eidx.push_back(i);
        }
        if (sidx.size() != eidx.size()) return false;
        for (int i = 0; i < sidx.size(); i++) {
            if (start[sidx[i]] != end[eidx[i]]) return false;
            if (start[sidx[i]] == 'L' && sidx[i] < eidx[i]) return false;
            if (start[sidx[i]] == 'R' && sidx[i] > eidx[i]) return false;
        }
        return true;
    }
};

JavaScript

function canTransform(start, end) {
    const sidx = [], eidx = [];
    const n = start.length;
    for (let i = 0; i < n; i++) {
        if (start[i] !== 'X') sidx.push(i);
        if (end[i] !== 'X') eidx.push(i);
    }
    if (sidx.length !== eidx.length) return false;
    for (let i = 0; i < sidx.length; i++) {
        if (start[sidx[i]] !== end[eidx[i]]) return false;
        if (start[sidx[i]] === 'L' && sidx[i] < eidx[i]) return false;
        if (start[sidx[i]] === 'R' && sidx[i] > eidx[i]) return false;
    }
    return true;
}

#include <stdbool.h>
#include <string.h>

bool canTransform(char *start, char *end) {
    int n = strlen(start), si = 0, ei = 0;
    char s[n], e[n];
    for (int i = 0; i < n; i++) {
        if (start[i] != 'X') s[si++] = start[i];
        if (end[i] != 'X') e[ei++] = end[i];
    }
    if (si != ei) return false;
    for (int i = 0; i < si; i++) {
        if (s[i] != e[i]) return false;
    }
    si = ei = 0;
    for (int i = 0; i < n; i++) {
        if (start[i] == 'L' && si < ei) return false;
        if (end[i] == 'R' && ei < si) return false;
        if (start[i] != 'X') si++;
        if (end[i] != 'X') ei++;
    }
    return true;
}

using System.Collections.Generic;

public class Solution {
    public bool CanTransform(string start, string end) {
        List<int> sidx = new List<int>(), eidx = new List<int>();
        int n = start.Length;
        for (int i = 0; i < n; i++) {
            if (start[i] != 'X') sidx.Add(i);
            if (end[i] != 'X') eidx.Add(i);
        }
        if (sidx.Count != eidx.Count) return false;
        for (int i = 0; i < sidx.Count; i++) {
            if (start[sidx[i]] != end[eidx[i]]) return false;
            if (start[sidx[i]] == 'L' && sidx[i] < eidx[i]) return false;
            if (start[sidx[i]] == 'R' && sidx[i] > eidx[i]) return false;
        }
        return true;
    }
}

Python leverages list comprehensions to accelerate index collection of 'L' and 'R' characters, measuring inequality and movement conformity exceedingly well.

Complexity

The time complexity is linear O(N), similar to space complexity being O(N).

Try this approach in the editor

Approach 3: Default Approach

func canTransform(start string, end string) bool {
	n := len(start)
	i, j := 0, 0
	for {
		for i < n && start[i] == 'X' {
			i++
		}
		for j < n && end[j] == 'X' {
			j++
		}
		if i == n && j == n {
			return true
		}
		if i == n || j == n || start[i] != end[j] {
			return false
		}
		if start[i] == 'L' && i < j {
			return false
		}
		if start[i] == 'R' && i > j {
			return false
		}
		i, j = i+1, j+1
	}
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Two Pointer Approach	With a time complexity of O(N) based on the linear traversal and constant space complexity O(1).
Index Matching Technique	The time complexity is linear O(N), similar to space complexity being O(N).
Default Approach	–

Complexity analysis

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.

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.

Swap Adjacent in LR String solution and explanation

The problem

Approach overview

Approach 1: Two Pointer Approach

Approach 2: Index Matching Technique

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Swap Adjacent in LR String solution and explanation

The problem

Approach overview

Approach 1: Two Pointer Approach

Approach 2: Index Matching Technique

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems