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

Move Pieces to Obtain a String

Difficulty: Medium

Problem Description

You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '' where 'L' and 'R' represent pieces that can move left and right respectively, and '' represents a blank space that can be occupied by any of the 'L' or 'R' pieces. Return true if it is possible to obtain the string target by moving the pieces of the string start any number of times. Otherwise, return false.

Key Insights

  • 'L' can only move to the left if there is a blank space directly to its left.
  • 'R' can only move to the right if there is a blank space directly to its right.
  • The positions of 'L' and 'R' in start and target must match in terms of their relative movement capabilities.
  • The number of 'L' and 'R' pieces must be the same in both strings for a transformation to be possible.

Space and Time Complexity

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

Solution

The solution involves using a two-pointer technique to traverse both strings simultaneously. We will maintain two pointers—one for the start string and one for the target string. We will move through both strings while checking the following conditions:

  1. If both characters at the pointers are the same (both 'L', both 'R', or both '_'), we can move both pointers forward.
  2. If the characters differ, we need to ensure that:
    • If we encounter 'L' in target, the corresponding character in start must be 'L' or '', and there must be enough '''s for it to move left.
    • If we encounter 'R' in target, the corresponding character in start must be 'R' or '', and there must be enough '''s for it to move right.
  3. If we reach the end of both strings simultaneously, the transformation is valid. If not, it is invalid.

Code Solutions

def canTransform(start: str, target: str) -> bool:
    # Initialize pointers for both strings
    i, j = 0, 0
    n = len(start)
    
    while i < n or j < n:
        # Skip underscores in both strings
        while i < n and start[i] == '_':
            i += 1
        while j < n and target[j] == '_':
            j += 1
        
        # If both pointers are at the end, transformation is valid
        if i == n and j == n:
            return True
        
        # If one pointer is at the end and the other is not, return False
        if (i == n) != (j == n):
            return False
        
        # Check if characters are the same
        if start[i] != target[j]:
            return False
        
        # Check movement conditions
        if start[i] == 'L' and i < j:
            return False
        if start[i] == 'R' and i > j:
            return False
        
        # Move to the next character
        i += 1
        j += 1
    
    return True
← Back to All Questions