Swap Adjacent in LR String - Practice Coding Problems

Swap Adjacent in LR String - 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.

Key insight: L can only move left, R can only move right, and their relative order must be preserved.

Input & Output

Example 1 — Basic Transformation

$ Input: start = "RXXLRXRXL", result = "XRLXXRRLX"

› Output: true

💡 Note: We can transform start to result: R can move right through X positions, L can move left through X positions. The sequence R,L,R,R,L is preserved in both strings.

Example 2 — Invalid Movement

$ Input: start = "R", result = "L"

› Output: false

💡 Note: Cannot change R to L - only movements allowed are XL→LX and RX→XR. Character types must remain the same.

Example 3 — Impossible Direction

$ Input: start = "XXLR", result = "LRXX"

› Output: false

💡 Note: L at position 2 cannot move right to position 0, and R at position 3 cannot move left to position 1. Movement constraints are violated.

Constraints

1 ≤ start.length, result.length ≤ 10⁴
start and result consist only of characters 'L', 'R', and 'X'

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings with L, R, X characters

Allowed Moves

XL→LX (L moves left), RX→XR (R moves right)

Output

True if start can be transformed to result

Key Takeaway

🎯 Key Insight: L and R characters can only move in their designated directions through X positions, and their relative order must be preserved.

Asked in

G Google 45 f Facebook 38 M Microsoft 29 a Amazon 22

The key insight is that L can only move left and R can only move right, while preserving their relative order. The optimal approach uses two pointers to match L/R characters in O(n) time while validating movement constraints. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Character Matching	O(n)	O(1)	One pass through both strings using pointers to match L/R characters
Brute Force Simulation	O(2^n)	O(2^n)	Try all possible move sequences using BFS/DFS until target is reached
Two Pointers with Movement Rules	O(n)	O(1)	Use two pointers to verify L/R positions and movement constraints

Single Pass Character Matching — Algorithm Steps

Initialize pointers for both strings
Skip X characters in both strings
Match L/R characters and check positions
Verify all characters are matched

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set pointers at start of both strings

Skip X

Advance pointers past X characters

Match & Validate

Compare L/R and check movement rules

Code -

solution.c — C

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

#define MAX_LEN 1000

bool solution(char* start, char* result) {
    int len = strlen(start);
    if (len != strlen(result)) return false;
    
    int i = 0, j = 0;
    
    while (i < len && j < len) {
        // Skip X in start string
        while (i < len && start[i] == 'X') i++;
        
        // Skip X in result string
        while (j < len && result[j] == 'X') j++;
        
        // Both reached end
        if (i == len && j == len) return true;
        
        // One reached end but not the other
        if (i == len || j == len) return false;
        
        // Characters must match
        if (start[i] != result[j]) return false;
        
        // Check movement constraints
        if (start[i] == 'L' && i < j) return false; // L cannot move right
        if (start[i] == 'R' && i > j) return false; // R cannot move left
        
        i++;
        j++;
    }
    
    // Skip remaining X characters
    while (i < len && start[i] == 'X') i++;
    while (j < len && result[j] == 'X') j++;
    
    return i == len && j == len;
}

int main() {
    char start[MAX_LEN], result[MAX_LEN];
    fgets(start, sizeof(start), stdin);
    fgets(result, sizeof(result), stdin);
    start[strcspn(start, "\n")] = 0;
    result[strcspn(result, "\n")] = 0;
    
    printf(solution(start, result) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through both strings with two pointers

✓ Linear Growth

Space Complexity

O(1)

Only uses two pointer variables, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

891 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Character Matching — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler