Coding Problem: Move Pieces to Obtain a String

Problem Statement

You are given two strings, start and target, both of length n. Each string consists of the characters 'L', 'R', and '_', where:

• The characters 'L' and 'R' represent pieces, where a piece 'L' can move to the left only if there is a blank space ('_') directly to its left, and a piece 'R' can move to the right only if there is a blank space directly to its right.
• The character '_' represents a blank space that can be occupied by any of the 'L' or 'R' pieces.

Your task is to determine if it is possible to obtain the target string from the start string by moving the pieces any number of times. If it is possible, return true; otherwise, return false.

Example 1:

Input: start = "_L__R__R_", target = "L______RR"

Output: true

Explanation: We can obtain the string target from start by doing the following moves:

• Move the first piece one step to the left, start becomes "L___R__R_".
• Move the last piece one step to the right, start becomes "L___R___R".
• Move the second piece three steps to the right, start becomes "L______RR".

Since it is possible to get the string target from start, we return true.

Example 2:

Input: start = "R_L_", target = "__LR"

Output: false

Explanation: The 'R' piece in the string start can move one step to the right to obtain "_RL_". After that, no pieces can move anymore, so it is impossible to obtain the string target from start. Thus, we return false.

Example 3:

Input: start = "_R", target = "R_"

Output: false

Explanation: The piece in the string start can move only to the right, so it is impossible to obtain the string target from start. Hence, we return false.

Approach to Solve the Problem

To determine whether it is possible to transform the start string into the target string, we can follow a simple approach:

• First, check if the number of 'L' and 'R' pieces in both the start and target strings are the same. If not, return false immediately.
• Then, iterate through both strings simultaneously. For each 'L' piece in the start string, ensure that it can be moved to the corresponding position in the target string (i.e., the position should allow movement to the left). Similarly, check for each 'R' piece that it can move to the corresponding position in the target string (i.e., the position should allow movement to the right).
• If all conditions are met, return true; otherwise, return false.

This approach ensures that we consider both the relative positions of the pieces and the available blank spaces.

Time Complexity

The time complexity of the solution is O(n), where n is the length of the strings. This is because we only need to iterate over the strings once to check the conditions and perform the necessary checks.

Code Implementation (Python)

def canTransform(start: str, target: str) -> bool:
    if start.replace('_', '') != target.replace('_', ''):
        return False

    start_indices, target_indices = [], []
    for i in range(len(start)):
        if start[i] != '_':
            start_indices.append(i)

    for i in range(len(target)):
        if target[i] != '_':
            target_indices.append(i)

    for i in range(len(start_indices)):
        if start_indices[i] > target_indices[i]:
            if start[start_indices[i]] == 'R':
                return False
        elif start_indices[i] < target_indices[i]:
            if start[start_indices[i]] == 'L':
                return False

    return True
            

The Python function canTransform implements the logic described above. It checks if the 'L' and 'R' pieces in the start and target strings are aligned correctly and can move accordingly.

For more coding challenges and solutions, visit our CodeToCareer Blog.