LeetCode 777 - Swap Adjacent in LR String

Difficulty: 🟡 Medium
Topics: Two Pointers, String

Solution

Problem Understanding

The problem gives us two strings, start and result, both consisting only of the characters 'L', 'R', and 'X'. We are allowed to transform the start string using only two kinds of moves:

Replace "XL" with "LX"
Replace "RX" with "XR"

The goal is to determine whether it is possible to transform start into result after applying any number of these valid moves.

To understand the problem more clearly, it helps to interpret what the characters mean in terms of movement.

The character 'L' can only move to the left because the only rule involving 'L' is "XL" → "LX". This means an 'L' can swap with an 'X' only if the 'X' is immediately to its left. Therefore, 'L' can never move right.

Similarly, the character 'R' can only move to the right because the rule "RX" → "XR" allows 'R' to swap with an 'X' immediately to its right. Therefore, 'R' can never move left.

The character 'X' acts as an empty placeholder. It is not really moving on its own, rather, 'L' and 'R' move through these empty spaces.

The expected output is a boolean:

Return True if start can be transformed into result
Return False otherwise

Constraints Analysis

The length of the strings can be as large as 10^4, which is important because it immediately suggests that expensive search-based approaches are unlikely to work efficiently.

Since both strings have the same length and only contain three possible characters, we should aim for a linear or near-linear time solution.

A naive simulation of all possible moves would quickly become infeasible because the number of reachable states grows exponentially.

Important Edge Cases

One important edge case occurs when the order of 'L' and 'R' differs between start and result. Since moves only swap with 'X', the relative order of non-'X' characters can never change. If the order differs, transformation is impossible.

Another edge case is when an 'L' appears farther to the right in result than in start. Since 'L' can only move left, such a transformation is invalid.

Similarly, an 'R' cannot move left. If an 'R' appears farther left in result than in start, the transformation must fail.

Cases involving only 'X', such as "X" to "X", should return True because no transformation is needed.

Approaches

Brute Force Approach

A brute force solution would simulate every possible valid move from the start string and try to eventually reach result.

This can be modeled as a graph search problem where:

Each string configuration is a node
Each valid transformation is an edge
We search for whether result is reachable

We could use Breadth-First Search (BFS) or Depth-First Search (DFS). At every state, we scan the string and generate all possible next states by applying:

"XL" → "LX"
"RX" → "XR"

This guarantees correctness because we eventually explore every reachable configuration.

However, this approach is far too slow. The number of possible intermediate states can grow exponentially with string length, making it impractical for n = 10^4.

Optimal Approach, Two Pointers and Movement Constraints

The key insight is that we do not need to simulate moves at all.

Instead, we can reason about the movement restrictions.

First, observe that removing all 'X' characters from both strings must produce the same sequence of 'L' and 'R'. Since only adjacent swaps with 'X' are allowed, 'L' and 'R' can never pass through each other or change order.

For example:

start  = "RXXLRXRXL"
result = "XRLXXRRLX"

Removing 'X' gives:

"RLRRL"
"RLRRL"

The order matches, so transformation might still be possible.

Next, we verify movement validity:

'L' can only move left, therefore its index in result must be less than or equal to its index in start
'R' can only move right, therefore its index in result must be greater than or equal to its index in start

We can check this efficiently using two pointers that skip 'X' and compare only meaningful characters.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores transformation states using BFS or DFS
Optimal	O(n)	O(1)	Uses two pointers and movement constraints

Algorithm Walkthrough

Initialize two pointers, i for start and j for result.

These pointers will traverse both strings while skipping 'X' characters because 'X' only represents empty space and does not affect ordering. 2. Skip all 'X' characters in both strings.

While start[i] == 'X', increment i.

While result[j] == 'X', increment j.

This ensures we compare only meaningful characters, 'L' and 'R'. 3. Check whether both pointers reached the end.

If both pointers are exhausted at the same time, the strings are compatible and transformation is possible.

If only one pointer reaches the end, the strings contain different numbers of non-'X' characters, making transformation impossible. 4. Compare the current characters.

If start[i] != result[j], return False.

This guarantees the relative order of 'L' and 'R' remains unchanged. 5. Validate movement rules.

If the character is 'L', check:

i >= j

Since 'L' can only move left, it cannot end up farther right.

If the character is 'R', check:

i <= j

Since 'R' can only move right, it cannot end up farther left. 6. Move both pointers forward.

Increment both i and j and continue scanning. 7. Continue until both strings are fully processed.

Why it works

The algorithm relies on two invariants.

First, the relative order of 'L' and 'R' cannot change because swaps only involve 'X'. Therefore, both strings must contain the same sequence of non-'X' characters.

Second, movement direction is restricted. 'L' can only move left, and 'R' can only move right. By validating index relationships during traversal, we guarantee every character movement is physically achievable.

Since these are the only restrictions imposed by the move rules, satisfying both conditions guarantees the transformation is possible.

Python Solution

class Solution:
    def canTransform(self, start: str, result: str) -> bool:
        n = len(start)
        i = 0
        j = 0

        while i < n or j < n:
            while i < n and start[i] == 'X':
                i += 1

            while j < n and result[j] == 'X':
                j += 1

            if i == n and j == n:
                return True

            if i == n or j == n:
                return False

            if start[i] != result[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

        return True

Implementation Explanation

The implementation begins by initializing two pointers, i and j, which track positions in start and result.

The main loop continues while either pointer remains inside the string. Before comparing characters, we skip all 'X' values because they are placeholders and not meaningful to ordering.

After skipping 'X', we handle termination cases. If both pointers reach the end simultaneously, the transformation is valid. If only one ends, the strings contain different non-'X' structures.

We then compare the current characters. If they differ, transformation is impossible because 'L' and 'R' cannot change order.

The next section enforces movement rules:

'L' must not move right, so i < j is invalid
'R' must not move left, so i > j is invalid

Finally, both pointers move forward to process the next meaningful character.

This implementation directly mirrors the algorithm and runs in linear time.

Go Solution

func canTransform(start string, result string) bool {
	n := len(start)
	i, j := 0, 0

	for i < n || j < n {
		for i < n && start[i] == 'X' {
			i++
		}

		for j < n && result[j] == 'X' {
			j++
		}

		if i == n && j == n {
			return true
		}

		if i == n || j == n {
			return false
		}

		if start[i] != result[j] {
			return false
		}

		if start[i] == 'L' && i < j {
			return false
		}

		if start[i] == 'R' && i > j {
			return false
		}

		i++
		j++
	}

	return true
}

Go-specific Notes

The Go implementation follows the same logic as the Python version.

Since Go strings are byte-indexable and the input contains only ASCII characters ('L', 'R', 'X'), direct indexing with start[i] is safe and efficient.

No special handling for nil values is required because strings in Go are immutable value types.

Integer overflow is not a concern because indices remain bounded by n ≤ 10^4.

Worked Examples

Example 1

start  = "RXXLRXRXL"
result = "XRLXXRRLX"

We track the two pointers while skipping 'X'.

Step	i	j	start[i]	result[j]	Action
1	0	1	R	R	Valid, R moved right
2	3	2	L	L	Valid, L moved left
3	4	5	R	R	Valid
4	6	6	R	R	Valid
5	8	7	L	L	Valid, L moved left
End	9	9	-	-	Return True

All characters match in order and satisfy movement constraints.

Result:

True

Example 2

start = "X"
result = "L"

Step	i	j	start[i]	result[j]	Action
1	1	0	End	L	One pointer exhausted

Since start has no non-'X' character but result still contains 'L', transformation is impossible.

Result:

False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer traverses the string at most once
Space	O(1)	Only a few variables are used

The algorithm is linear because each pointer advances monotonically through the string without backtracking. Even though nested loops appear in the implementation, every character is visited at most once by each pointer.

The space complexity is constant because no extra data structures proportional to input size are allocated.

Test Cases

solution = Solution()

assert solution.canTransform("RXXLRXRXL", "XRLXXRRLX") is True  # Provided example
assert solution.canTransform("X", "L") is False  # Provided impossible case

assert solution.canTransform("X", "X") is True  # Single identical placeholder
assert solution.canTransform("L", "L") is True  # Single identical character
assert solution.canTransform("R", "R") is True  # Single identical character

assert solution.canTransform("XL", "LX") is True  # L moves left
assert solution.canTransform("RX", "XR") is True  # R moves right

assert solution.canTransform("LX", "XL") is False  # L cannot move right
assert solution.canTransform("XR", "RX") is False  # R cannot move left

assert solution.canTransform("RL", "LR") is False  # Relative order changes
assert solution.canTransform("RXL", "XRL") is True  # Valid mixed movement
assert solution.canTransform("XXRXXLXXXX", "XXXXRXXLXX") is False  # Invalid R movement

assert solution.canTransform("XXXX", "XXXX") is True  # All placeholders
assert solution.canTransform("LXXLXRLXXL", "XLLXRXLXLX") is False  # Complex invalid case

Test	Why
`"RXXLRXRXL" → "XRLXXRRLX"`	Valid complex transformation
`"X" → "L"`	Different non-`X` structure
`"X" → "X"`	Minimal valid input
`"L" → "L"`	Single matching character
`"R" → "R"`	Single matching character
`"XL" → "LX"`	Valid left movement
`"RX" → "XR"`	Valid right movement
`"LX" → "XL"`	Invalid right movement for `L`
`"XR" → "RX"`	Invalid left movement for `R`
`"RL" → "LR"`	Order cannot change
`"RXL" → "XRL"`	Valid mixed movement
`"XXRXXLXXXX" → "XXXXRXXLXX"`	`R` attempts illegal left movement
`"XXXX" → "XXXX"`	Only placeholders
Complex invalid case	Stress test for pointer logic

Edge Cases

Different Non-`X` Character Order

A subtle bug occurs when start and result contain the same characters but in a different order.

Example:

start  = "RL"
result = "LR"

A naive implementation might try to simulate swaps and accidentally assume reordering is possible. However, since swaps only occur with 'X', 'L' and 'R' can never pass through each other. The implementation catches this because the pointer comparison finds mismatched characters.

Illegal Direction Movement

Another important case happens when a character moves in a forbidden direction.