Problem of The Day: Move Pieces to Obtain a String

Problem Statement

Intuition

When I first looked at this problem, I noticed that the movement of characters L and R is constrained by the fact that L can only move to the left and R can only move to the right. This led me to the realization that the order and types of non-underscore (_) characters must be identical in both start and target, and their positions must also respect these movement constraints.

Approach

My approach begins by isolating the characters and their indices from both the start and target strings, ignoring underscores (_). This helps to focus only on the significant movements of L and R.

1. First, I extract two lists: one for the characters (start_str and target_str) and one for their indices (start_index and target_index).
2. I then compare the extracted characters (start_str and target_str). If they are not identical, it is impossible to rearrange start into target.
3. Next, I iterate through the indices to ensure that each L in start is not attempting to move right (by checking that its index is greater than or equal to its corresponding index in target). Similarly, each R in start must not move left (its index must be less than or equal to its target index).

If all these checks pass, then it is possible to transform start into target.

Complexity

• Time complexity: \(O(n)\)
  Extracting the characters and indices from both strings involves a single pass through each string, and the final comparison involves iterating through the indices, which is linear.

• Space complexity: \(O(n)\)
  Additional space is used to store the extracted characters and their indices for both strings.

Code

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        start_str = []
        start_index = []
        target_str = []
        target_index = []

        for i, c in enumerate(start):
            if c != '_':
                start_str.append(c)
                start_index.append(i)

        for i, c in enumerate(target):
            if c != '_':
                target_str.append(c)
                target_index.append(i)

        if start_str != target_str:
            return False

        for i in range(len(target_index)):
            if start_str[i] == 'L' and start_index[i] < target_index[i]:
                return False
            if start_str[i] == 'R' and start_index[i] > target_index[i]:
                return False

        return True

Editorial

Approach 2: Using Queue

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        # Queue to store characters and indices from both strings
        start_queue = []
        target_queue = []

        # Record non-underscore characters and their indices
        for i in range(len(start)):
            if start[i] != "_":
                start_queue.append((start[i], i))
            if target[i] != "_":
                target_queue.append((target[i], i))

        # If number of pieces don't match, return false
        if len(start_queue) != len(target_queue):
            return False

        # Compare each piece's type and position
        while not len(start_queue) == 0:
            start_char, start_index = start_queue.pop(0)
            target_char, target_index = target_queue.pop(0)

            # Check character match and movement rules
            if (
                start_char != target_char
                or (start_char == "L" and start_index < target_index)
                or (start_char == "R" and start_index > target_index)
            ):
                return False

        return True

Approach 3: Two pointer

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        start_length = len(start)
        # pointers for start string and target string
        start_index, target_index = (0, 0)

        while start_index < start_length or target_index < start_length:
            # skip underscores in start
            while start_index < start_length and start[start_index] == "_":
                start_index += 1

            # skip underscores in target
            while target_index < start_length and target[target_index] == "_":
                target_index += 1

            # if one string exhausted, both strings should be exhausted
            if start_index == start_length or target_index == start_length:
                return (
                    start_index == start_length and target_index == start_length
                )

            # check if the pieces match and follow movement rules
            if (
                start[start_index] != target[target_index]
                or (start[start_index] == "L" and start_index < target_index)
                or (start[start_index] == "R" and start_index > target_index)
            ):
                return False

            start_index += 1
            target_index += 1

        # if all conditions satisfied, return true
        return True