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.

Description Hints 1 Solution Video 12:28

777. Swap Adjacent in LR String

Medium38.5% acceptance3 companies

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'.

Asked at 3 companies

Lg Electronics

Google Bloomberg

Topics

String Two Pointers

Hints open one at a time

Hint 1

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.

12:28

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution