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

Move Pieces to Obtain a String

Number: 2414

Difficulty: Medium

Paid? No

Companies: Google, Meta, Amazon

Problem Description

Given two strings, start and target, consisting of the characters 'L', 'R', and '_' (blank), determine if it is possible to transform start into target by moving pieces under these rules:

  • An 'L' piece can move only to the left into an adjacent blank.
  • An 'R' piece can move only to the right into an adjacent blank. Return true if such a transformation is possible; otherwise, return false.

Key Insights

  • The relative order of the pieces (ignoring blanks) must remain the same in both strings.
  • 'L' pieces cannot move to the right and 'R' pieces cannot move to the left.
  • Use two pointers to simultaneously track the positions of the pieces (ignoring '_'s) in start and target.
  • For each matching piece:
    • If the piece is 'L', its position in start must be >= its position in target since it can only move left.
    • If the piece is 'R', its position in start must be <= its position in target since it can only move right.

Space and Time Complexity

Time Complexity: O(n) since we scan through the strings at most twice. Space Complexity: O(n) in the worst case due to the auxiliary arrays (if implemented that way), though it can be optimized to O(1) using pointers directly.

Solution

The solution begins by filtering out the blank characters from both start and target strings. If these resulting sequences do not match, then it is impossible to transform start into target.

Next, use two pointers to iterate over start and target simultaneously, comparing the positions of the 'L' and 'R' pieces. For every piece:

  • For an 'L', check that the index in start is not to the left of the index in target because it can only move left.
  • For an 'R', check that the index in start is not to the right of the index in target because it can only move right.

If all checks are satisfied, return true; otherwise, return false.

Code Solutions

# Python solution for "Move Pieces to Obtain a String"
def canChange(start: str, target: str) -> bool:
    # Filter out the blank characters.
    filtered_start = [c for c in start if c != '_']
    filtered_target = [c for c in target if c != '_']
    
    # Check if the sequences (order of pieces) match.
    if filtered_start != filtered_target:
        return False

    # Two pointers to compare positions in the start and target.
    i, j = 0, 0
    n = len(start)
    while i < n and j < n:
        # Move pointer i if it's pointing to a blank.
        while i < n and start[i] == '_':
            i += 1
        # Move pointer j if it's pointing to a blank.
        while j < n and target[j] == '_':
            j += 1
        # If both pointers are in bound, compare the characters.
        if i < n and j < n:
            if start[i] != target[j]:
                return False
            # For 'L' piece, it should not move right.
            if start[i] == 'L' and i < j:
                return False
            # For 'R' piece, it should not move left.
            if start[i] == 'R' and i > j:
                return False
            i += 1
            j += 1
    return True

# Example usage:
# print(canChange("_L__R__R_", "L______RR"))  # Expected output: True
← Back to All Questions