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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Swap Adjacent in LR String

Number: 793

Difficulty: Medium

Paid? No

Companies: Google, Adobe

Problem Description

Given two strings, start and result, composed of the characters 'L', 'R', and 'X', determine if there exists a sequence of moves to transform start into result. In one move, you can replace an occurrence of "XL" with "LX" or an occurrence of "RX" with "XR".

Key Insights

  • After removing all 'X' characters from both start and result, the strings must be identical; otherwise, transformation is impossible.
  • The moves have positional constraints:
    • For 'L' pieces: They can only move to the left, so each 'L' in start must not appear to the left of its corresponding 'L' in result.
    • For 'R' pieces: They can only move to the right, so each 'R' in start must not appear to the right of its corresponding 'R' in result.
  • A two-pointer approach can be used to compare corresponding characters in both strings (skipping 'X') and check the above positional conditions.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the input strings
Space Complexity: O(n) in the worst-case for storing filtered characters (can be optimized to O(1) using pointers only)

Solution

We start by removing all 'X' characters from both start and result. If the resulting strings of 'L' and 'R' are not identical, the transformation is not possible. Next, we use two pointers to traverse both strings while skipping 'X'. For each corresponding position, we check:

  • If the characters differ, then it's impossible to transform.
  • If the character is 'L', its index in start should be greater than or equal to its index in result (because 'L' can only move to the left).
  • If the character is 'R', its index in start should be less than or equal to its index in result (because 'R' can only move to the right). If all these conditions are satisfied and any remaining characters in both strings are only 'X', then the transformation is possible.

Code Solutions

# Python solution using two pointers
class Solution:
    def canTransform(self, start: str, result: str) -> bool:
        n = len(start)
        # Check that the sequence of L and R without X is the same in both strings.
        filteredStart = ''.join([ch for ch in start if ch != 'X'])
        filteredResult = ''.join([ch for ch in result if ch != 'X'])
        
        if filteredStart != filteredResult:
            return False

        i, j = 0, 0
        
        # Use two pointers to traverse the strings
        while i < n and j < n:
            # Skip 'X' in start
            while i < n and start[i] == 'X':
                i += 1
            # Skip 'X' in result
            while j < n and result[j] == 'X':
                j += 1

            # If both pointers are within bounds, compare the letters
            if i < n and j < n:
                if start[i] != result[j]:
                    return False
                # For 'L', ensure it does not move right.
                if start[i] == 'L' and i < j:
                    return False
                # For 'R', ensure it does not move left.
                if start[i] == 'R' and i > j:
                    return False
                i += 1
                j += 1
        
        return True
← Back to All Questions