We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Swap Adjacent in LR String

Difficulty: Medium

Problem Description

In a string composed of 'L', 'R', and 'X' characters, 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 Insights

  • The characters 'X' can move freely and do not affect the relative positions of 'L' and 'R'.
  • The order of 'L' and 'R' must be preserved, meaning that 'L' can only move left and 'R' can only move right.
  • The number of 'L', 'R', and 'X' characters must match between start and result.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a two-pointer approach to traverse both strings simultaneously. The idea is to iterate through both strings while ensuring that:

  1. The count of 'L' and 'R' characters is the same in both strings.
  2. The order of 'L' and 'R' in start is preserved in result. Specifically, we can only move 'L' to the left and 'R' to the right. The pointer for start should not pass the pointer for result for 'L', and vice versa for 'R'.

We will use two pointers, one for each string, and move them based on the character encountered.

Code Solutions

def canTransform(start: str, end: str) -> bool:
    if start.replace('X', '') != end.replace('X', ''):
        return False
    
    i, j = 0, 0
    n = len(start)
    
    while i < n and j < n:
        while i < n and start[i] == 'X':
            i += 1
        while j < n and end[j] == 'X':
            j += 1
        if i < n and j < n:
            if start[i] != end[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
        else:
            break
            
    return True
← Back to All Questions