Swap Adjacent in LR String

Swap Adjacent in LR String

What is this problem about?

The Swap Adjacent in LR String coding problem focuses on transforming one string into another using specific move rules. You are given a start string and a target string, both consisting of 'L', 'R', and 'X' characters. The rules are: 'LX' can be replaced by 'XL' (meaning 'L' can move left), and 'XR' can be replaced by 'RX' (meaning 'R' can move right). You need to determine if it is possible to transform the start string into the target string through any number of these moves.

Why is this asked in interviews?

This question is a favorite at Google because it tests a candidate's ability to identify invariants in a transformation problem. It evaluates whether you can move beyond simple simulation and instead find the underlying constraints that must hold true for a transformation to be possible. It checks your proficiency with string manipulation and the two-pointer technique, as well as your logical reasoning regarding the relative positions of characters.

Algorithmic pattern used

The primary pattern used is the Two Pointers and Invariant Checking pattern. There are three key observations:

1. If you remove all 'X' characters from both strings, the remaining 'L' and 'R' characters must be identical in order and count.
2. An 'L' in the start string can only move to an index in the target string that is less than or equal to its current index.
3. An 'R' in the start string can only move to an index in the target string that is greater than or equal to its current index. Using two pointers, you iterate through the non-'X' characters of both strings and verify these conditions.

Example explanation

start = "XRLX", target = "RXLX"

1. Non-'X' characters: both are "RL". (Match!)
2. 'R' in start is at index 1. 'R' in target is at index 0.
   • Wait, 'R' can only move to the right. Index 0 is to the left.
   • Result: False. start = "XLX", target = "LXX"
3. Non-'X' characters: both are "L". (Match!)
4. 'L' in start is at index 1. 'L' in target is at index 0.
   • 'L' can move left. Index 0 is to the left of 1.
   • Result: True.

Common mistakes candidates make

One common mistake is trying to use BFS or some other state-space search, which is far too slow given the potential length of the strings. Another error is forgetting that 'L' and 'R' cannot cross each other. Some candidates also fail to check the relative indices correctly, allowing 'L' to move right or 'R' to move left, which violates the movement rules.

Interview preparation tip

When preparing for the Swap Adjacent in LR String interview question, focus on identifying "what stays the same" (invariants). This is a common theme in string transformation problems. Practice using the Two Pointers interview pattern to skip over "filler" characters (like 'X' in this case) and compare the meaningful ones directly.