• Leetcode POTDs

Problem 2337 Move Pieces to Obtain a String

Problem Statement

Link - Problem 2337

Question

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.

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 equal to "L___R__R_".
- Move the last piece one step to the right, start becomes equal to "L___R___R".
- Move the second piece three steps to the right, start becomes equal to "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.

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.

Constraints:

• n == start.length == target.length
• 1 <= n <= 105
• start and target consist of the characters 'L', 'R', and '_'.

Solution

class Solution {
public:
    bool canChange(string start, string target) {
        int len = start.size();
        int start_ind = 0, target_ind = 0;

        while (start_ind < len || target_ind < len) {
            while (start_ind < len && start[start_ind] == '_') {
                start_ind++;
            }
            while (target_ind < len && target[target_ind] == '_') {
                target_ind++;
            }

            if (start_ind == len || target_ind == len) {
                return start_ind == len && target_ind == len;
            }

            if (start[start_ind] != target[target_ind])
                return false;
            if (start[start_ind] == 'L' && start_ind < target_ind)
                return false;
            if (start[start_ind] == 'R' && start_ind > target_ind)
                return false;

            start_ind++;
            target_ind++;
        }

        return true;
    }
};

Complexity Analysis

| Algorithm             | Time Complexity | Space Complexity |
| --------------------- | --------------- | ---------------- |
| Two-pointer traversal | O(n)            | O(1)             |

Explanation

Intial Thoughts

To solve this problem, we need to understand the rules of movement. Start by considering each piece (‘L’ and ‘R’) and how it can move to either the left or the right by potentially shifting through a blank space (’’). A key realization is that if ‘L’ is to the right of ‘R’ in the start string, it’s impossible to change the positions, and this must also hold true for the target string. Next, consider that moving a piece will shift it one space, so checking for consecutive movements may be essential. Lastly, think about how you might remove excess information from the problem and focus only on the essential details - the positions of ‘L’s and ‘R’s alone, as spaces (’’) don’t affect the overall outcome.

Intuitive Analysis

Further reflection reveals that finding the positions of ‘L’s and ‘R’s in the start and target strings may not be enough. Think of comparing them directly instead - maybe aligning them on the same indices might provide insight. When a non-space character is encountered in both strings, compare the characters to verify they match, check if the movement was possible, and move to the next non-space characters in both strings. By essentially pairing the start characters with the target characters based on the positioning rules and non-space comparison, we are essentially validating whether each character’s shift from start to target makes sense in one sweep. Overall, considering indexing, spacing, and matching pieces simplifies the complexity of determining possible movements. So try combining these observations in your problem-solving strategy.

1. Intuition

• The problem can be solved by comparing the positions of the pieces in the start and target strings.
• We can ignore the blank spaces in the strings and focus on the positions of the pieces.
• If the pieces in the start string can be moved to the positions of the pieces in the target string, then it is possible to obtain the target string.
• We need to check if the pieces in the start string can be moved to the positions of the pieces in the target string without crossing each other.
• If a piece in the start string is to the right of the corresponding piece in the target string, then it is not possible to obtain the target string.
• We can use two pointers to iterate through the start and target strings and compare the positions of the pieces.
• If we find a piece in the start string that cannot be moved to the position of the corresponding piece in the target string, then we return false.

2. Implementation

• We initialize two pointers, start_ind and target_ind, to the beginning of the start and target strings, respectively.
• We use two while loops to skip the blank spaces in the start and target strings.
• We compare the pieces at the current positions of the start and target strings.
• If the pieces are different, we return false.
• If the piece in the start string is ‘L’ and it is to the right of the corresponding piece in the target string, we return false.
• If the piece in the start string is ‘R’ and it is to the left of the corresponding piece in the target string, we return false.
• We increment the pointers and repeat the process until we reach the end of the start or target string.

Complexity Analysis

Time Complexity:

• The time complexity of this solution is dominated by the while loops that traverse the start and target strings. Both loops iterate at most n times, where n is the length of the strings.
• Inside the loops, constant-time operations are performed, such as comparing characters and incrementing indices.
• Since the loops are not nested, the overall time complexity is linear, proportional to the length of the input strings, hence O(n).
• Both the best and worst-case scenarios have the same time complexity because the loops always iterate through the entire strings, regardless of the arrangement of characters.

Space Complexity:

• The space complexity of this solution is constant because it only uses a fixed amount of space to store the indices start_ind and target_ind.
• No additional data structures are used that scale with the input size, and the input strings are not modified.
• The space complexity is O(1) because the memory usage does not grow with the size of the input strings.

Footnote

This question is rated as Medium difficulty.

Hints

After some sequence of moves, can the order of the pieces change?

Try to match each piece in s with a piece in e.

Similar Questions: