Coding Problem: Move Pieces to Obtain a String - Solution

Problem Statement

You are given two strings start and target, both of length n. Each string consists only 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.

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.

Approach

To solve this problem, consider the following steps:

1. Check character counts: Since the character 'L' and 'R' can move around but cannot change the order relative to each other, we first need to ensure that both strings have the same count of 'L', 'R', and '_'. If they don't match in character counts, it is immediately impossible to transform start into target, so return false.
2. Check positions for feasibility: After confirming the character counts match, we need to check if the relative movement of the pieces is possible. Specifically:
   • All 'L' characters in the start string must be able to move leftwards to match the positions of 'L' characters in target.
   • Similarly, all 'R' characters must be able to move rightwards.
   • The blank spaces ('_') in both strings are simply placeholders and do not affect the movement rules of 'L' and 'R'.
3. Final check: Given that the movement of 'L' and 'R' pieces only depends on their relative positions, we need to ensure that the positions of 'L' and 'R' pieces in start can be transformed into those in target.

Code Implementation

def canChange(start: str, target: str) -> bool:
    # Check if both strings have the same number of L's and R's
    if start.replace('_', '') != target.replace('_', ''):
        return False
    
    n = len(start)
    start_filtered = []
    target_filtered = []
    
    # Filter out '_' characters and only consider L's and R's
    for i in range(n):
        if start[i] != '_':
            start_filtered.append((start[i], i))
        if target[i] != '_':
            target_filtered.append((target[i], i))
    
    # Check if the filtered versions are identical
    if len(start_filtered) != len(target_filtered):
        return False
    
    for (s, si), (t, ti) in zip(start_filtered, target_filtered):
        # For 'L', we need it to move to the left; for 'R', it needs to move to the right.
        if s == 'L' and si < ti:
            return False
        if s == 'R' and si > ti:
            return False
    
    return True
        

Explanation of the Code

1. Initial check for character counts: We start by comparing the strings start and target after removing the blank spaces ('_'). If the remaining characters don't match, we return false immediately.

2. Filtering the non-blank characters: Next, we create two filtered lists start_filtered and target_filtered that contain only the non-blank characters and their respective indices. These lists will hold pairs of (character, index) for both start and target.

3. Position check: We then check if the relative positions of 'L' and 'R' pieces in the start string can match those in the target string. Specifically:

• An 'L' piece in start can only move to the left, so if its position in start is less than its corresponding position in target, it is not possible to move it, so we return false.
• An 'R' piece in start can only move to the right, so if its position in start is greater than its corresponding position in target, it is also not possible to move it, so we return false.

4. Return true if all checks pass: If all checks pass, we return true, meaning it's possible to transform start into target.

Time Complexity

Time complexity: O(n), where n is the length of the strings. This is because we only traverse the strings a few times (once to filter out blanks and once to check positions).

Space complexity: O(n), due to the space required to store the filtered lists of non-blank characters.

Example

# Test Case 1
start = "_R_L_"
target = "R_L_"
print(canChange(start, target))  # Output: True

# Test Case 2
start = "R_L_"
target = "RL__"
print(canChange(start, target))  # Output: False

# Test Case 3
start = "_R_"
target = "_R_"
print(canChange(start, target))  # Output: True
        

Conclusion: This solution ensures that the relative positions of the pieces are respected while transforming start into target. The approach is efficient, and the time complexity is linear, making it well-suited for large inputs.

Resource	Link
Follow us on Linkedin	Click Here
Ways to get your next job	Click Here
How your resume should be to attract companies	Click Here
Check Out Jobs	Click Here
Read our blogs	Click Here