Abstract / Summary

Check if you can turn one string into another by repeatedly swapping adjacent letters l and r.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 38% (200k+ submissions).

Typical patterns to solve this problem:

• String
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether one string can be transformed into another under a set of movement rules for the characters L, R, and X. The transformation permits L to move only leftward, R to move only rightward, and X to act as an empty placeholder. The algorithm proceeds through a series of logical checks that enforce ordering constraints, verify matching counts, and ensure that each movable character respects its directional limits.

Order Preservation Check

The first logical gate removes all placeholder characters (X) from both strings and compares the resulting sequences. Because L and R cannot cross each other, their relative order must be identical in the source and target strings. The code snippet that performs this validation is:

if start.replace("X", "") != end.replace("X", ""):
    return False

If the stripped strings differ, the transformation is impossible, and the function exits early.

Index Collection

To enforce directional constraints, the algorithm records the positions of each R and L in both the start and end strings. This is achieved with list comprehensions that iterate over the enumerated characters:

r1 = [i for i, c in enumerate(start) if c == "R"]
r2 = [i for i, c in enumerate(end)   if c == "R"]
l1 = [i for i, c in enumerate(start) if c == "L"]
l2 = [i for i, c in enumerate(end)   if c == "L"]

These lists capture the exact indices where each movable character appears, enabling direct comparison of their allowed movement ranges.

Length Consistency

Before examining individual positions, the code confirms that the counts of R (and implicitly L) match between the two strings. A mismatch in the number of movable characters makes any transformation impossible:

if len(r1) != len(r2):
    return False
# now len(l1) == len(l2), too

The comment clarifies that the equality of L counts follows automatically from the earlier order preservation check.

Direction Constraints for R

The rule that R may only move rightward translates to a requirement that each R in the start string must not be positioned to the right of its counterpart in the end string. The algorithm iterates over paired indices and returns False if any R violates this constraint:

for a, b in zip(r1, r2):
    if a > b:
        return False

If all R positions satisfy a <= b, the rightward movement condition holds.

Direction Constraints for L

Similarly, L may only move leftward, which means each L in start must not be positioned to the left of its counterpart in end. The corresponding loop checks this condition:

for a, b in zip(l1, l2):
    if a < b:
        return False

A violation (a < b) indicates an illegal rightward shift for L, causing the function to reject the transformation.

Edge Cases Handled

The implementation gracefully handles several edge scenarios:

• Identical strings: The initial order check passes, the index lists are equal, and both directional loops find no violations, resulting in True.
• Strings composed solely of X: After stripping X, both become empty, satisfying the order check; the index lists are empty, and the loops are bypassed, yielding True.
• Strings where one contains extra L or R characters: The length consistency check detects the discrepancy and returns False.
• Situations where an R appears to the right of its target position or an L appears to the left of its target: The directional loops catch these cases and reject the transformation.

Performance Optimizations

The algorithm leverages early exits to avoid unnecessary work. The order preservation check and length consistency check are performed before any index traversal, allowing the function to terminate quickly for clearly invalid inputs. The use of list comprehensions to collect indices runs in linear time and produces compact data structures that are then iterated in lockstep using zip, which stops as soon as the shorter list ends. This approach minimizes the number of comparisons and avoids redundant scanning of the strings after the initial passes. The overall flow ensures that each character of the input strings is examined a constant number of times, leading to an efficient solution for the problem size.

Imagine there is a toy box with three types of pieces: R, L, and X. X pieces are just empty spaces where other pieces can slide into. R pieces are little red cars that only like to move to the right side of the box. L pieces are little blue cars that only like to move to the left side of the box. Because R cars only go right and L cars only go left, they can never jump over each other.

The code first checks the box to make sure there is the same number of red cars and blue cars at the start and the end. Then it looks at all the red cars to make sure every one of them ends up in a spot that is the same or to the right of where it started. Finally, it looks at all the blue cars to make sure every one of them ends up in a spot that is the same or to the left of where it started. If all the red cars and blue cars follow their rules and end up in the right spots without jumping over each other, then the puzzle is solved.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++					Python	Java			TS
	WalkCCC	C++					Python	Java
	leetcode.ca	C++					Python	Java		Go
	LeetcodeHelp	C++					Python	Java
	Progiez	C++					Python	Java
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai							Java
	everthis		JS
	fengvyi	C++
	JoshCrozier		JS
	lkwq007						Python
	lzl124631x	C++
	martianoff				Scala
	ruoru					Rust
	suxrobGM			C#
	vli02								C
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
JoshCrozier	JavaScript
lkwq007	Python
lzl124631x	C++
martianoff	Scala
ruoru	Rust
suxrobGM	C#
vli02	C
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality