2337. Move Pieces to Obtain a String


Problem Description

The given problem is about transforming one string into another using specific movement rules for the characters within the strings. The strings start and target are of the same length n and consist only of characters 'L', 'R', and ''. An 'L' can move only left if there is a blank space ('') directly to its left, and an 'R' can move only right if there is a blank space directly to its right. The goal is to determine if the start string can be transformed into the target string by applying these movements any number of times. The output should be true if the transformation is possible, otherwise false.

Intuition

The intuition behind the solution involves two key insights:

  1. The relative order of the pieces 'L' and 'R' cannot change because 'L' can only move left and 'R' can only move right. Therefore, if in the target string, an 'R' appears to the left of an 'L' which was to its right in the start string, the transformation is not possible.

  2. Given the same relative order, an 'L' can only move to the left, so its position in the target string must not be to the right of its position in the start string. Similarly, an 'R' can only move to the right, so its position in the target string must not be to the left of its position in the start string.

With these insights in mind, the solution approach is straightforward:

  • Ignore the blank spaces and compare the positions of the non-blank characters in both strings. If there are a different number of 'L' and 'R' characters or they are in a different relative order, the target cannot be reached.

  • If the characters are in the same order, check if 'L' in target is never to the right of its position in start, and 'R' is never to the left. If this is true for all characters, then the transformation is possible and return true. Otherwise, return false.

Learn more about Two Pointers patterns.

Solution Approach

The Python code provided earlier implements the solution approach effectively. It uses the following steps and Python-specific data structures and functions:

  1. Filtering and Pairing: The comprehension lists a and b filter out the blank spaces '_' and create lists of tuples that contain the character and its index (position) from the start and target strings, respectively. This is done using the enumerate function which gives the index along with each character as you iterate over the string:

    1a = [(v, i) for i, v in enumerate(start) if v != '_']
    2b = [(v, i) for i, v in enumerate(target) if v != '_']
  2. Checking the Length: This step checks if the lengths of the filtered lists are equal. If they are not, it is not possible to get target from start since the number of movable pieces is different, so the function returns False.

    1if len(a) != len(b):
    2    return False
  3. Comparing Corresponding Pairs: The use of the zip function takes pairs from a and b in a parallel manner to ensure we're comparing pieces from the start and target strings that are supposed to correspond to each other.

  4. Piece Type and Position Validation: For each pair of tuples (c, i) from a, and (d, j) from b, the following checks are performed:

    • If the piece type is not the same (c != d), it cannot be a valid transformation since 'L' cannot become 'R' and vice versa, hence False is returned.
    • If the piece is 'L', it should not be to the right in target as compared to start (i < j case), since 'L' can only move left.
    • If the piece is 'R', it should not be to the left in target as compared to start (i > j case), since 'R' can only move right.

    If any of these conditions are violated, the function returns False.

    1for (c, i), (d, j) in zip(a, b):
    2    if c != d or (c == 'L' and i < j) or (c == 'R' and i > j):
    3        return False
  5. Returning True: If none of the above checks fail, it means the transformation from start to target is possible, hence True is returned at the end of the function.

By using tuples for storing character and index pairs, and the zip function to iterate over them, we avoid the need for more complex data structures. This simplifies the algorithm and improves its readability and performance.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider two strings as an example:

  • start: "R__L"
  • target: "__RL"

Following the steps of the solution approach:

  1. Filtering and Pairing:

    For start:

    1a = [(v, i) for i, v in enumerate("R__L") if v != '_']
    2  = [('R', 0), ('L', 3)]

    For target:

    1b = [(v, i) for i, v in enumerate("__RL") if v != '_']
    2  = [('R', 2), ('L', 3)]
  2. Checking the Length:

    Length of a: 2 Length of b: 2

    Since both lengths are equal, we proceed.

  3. Comparing Corresponding Pairs:

    We utilize zip to compare each pair from a and b.

    Pairs to compare:

    1('R', 0) from `start` and ('R', 2) from `target`
    2('L', 3) from `start` and ('L', 3) from `target`
  4. Piece Type and Position Validation:

    For the first pair:

    • Piece type is the same, both are 'R'.
    • 'R' is in position 0 in start and position 2 in target, which is a valid move for 'R', since it can move to the right.

    For the second pair:

    • Piece type is the same, both are 'L'.
    • 'L' is in position 3 in start and position 3 in target, indicating no movement, which is also valid since 'L' cannot move to the right.

    Since both pairs are valid according to the movement rules, we can continue.

  5. Returning True:

    Because none of the validation checks failed, the function would return True, meaning it is possible to transform the start string "R__L" into the target string "__RL" by moving the 'R' two spaces to the right.

Solution Implementation

1class Solution:
2    def canChange(self, start: str, target: str) -> bool:
3        # Create pairs of (character, index) for non '_' characters in start string.
4        start_positions = [(char, index) for index, char in enumerate(start) if char != '_']
5      
6        # Create pairs of (character, index) for non '_' characters in target string.
7        target_positions = [(char, index) for index, char in enumerate(target) if char != '_']
8      
9        # If the number of non '_' characters in start and target are different, return False.
10        if len(start_positions) != len(target_positions):
11            return False
12      
13        # Iterate over the pairs of start and target together.
14        for (start_char, start_index), (target_char, target_index) in zip(start_positions, target_positions):
15            # If the characters are not the same, the transformation is not possible.
16            if start_char != target_char:
17                return False
18            # A 'L' character in start should have an index greater than or equal to that in target.
19            if start_char == 'L' and start_index < target_index:
20                return False
21            # A 'R' character in start should have an index less than or equal to that in target.
22            if start_char == 'R' and start_index > target_index:
23                return False
24      
25        # If all conditions are met, return True indicating the transformation is possible.
26        return True
27
1class Solution {
2    // Main method to check if it's possible to transform the start string to the target string
3    public boolean canChange(String start, String target) {
4        // Parse the strings to obtain the positions and types of 'L' and 'R' characters
5        List<int[]> startPosList = parseString(start);
6        List<int[]> targetPosList = parseString(target);
7
8        // If the number of 'L' and 'R' characters in both strings is different, transformation is not possible
9        if (startPosList.size() != targetPosList.size()) {
10            return false;
11        }
12
13        // Compare the positions and types of 'L' and 'R' characters in the two lists
14        for (int i = 0; i < startPosList.size(); ++i) {
15            int[] startPos = startPosList.get(i);
16            int[] targetPos = targetPosList.get(i);
17
18            // If the types of characters (L or R) are different at any point, transformation is not possible
19            if (startPos[0] != targetPos[0]) {
20                return false;
21            }
22            // If 'L' in start is to the right of 'L' in target, transformation is not possible as 'L' only moves left
23            if (startPos[0] == 1 && startPos[1] < targetPos[1]) {
24                return false;
25            }
26            // If 'R' in start is to the left of 'R' in target, transformation is not possible as 'R' only moves right
27            if (startPos[0] == 2 && startPos[1] > targetPos[1]) {
28                return false;
29            }
30        }
31        // All checks passed, transformation is possible
32        return true;
33    }
34
35    // Helper method to parse a string to a list of positions and types for 'L' and 'R'
36    private List<int[]> parseString(String s) {
37        List<int[]> result = new ArrayList<>();
38        for (int i = 0; i < s.length(); ++i) {
39            char currentChar = s.charAt(i);
40            // If the current character is 'L', add to the list with type 1
41            if (currentChar == 'L') {
42                result.add(new int[] {1, i});
43            }
44            // If the current character is 'R', add to the list with type 2
45            else if (currentChar == 'R') {
46                result.add(new int[] {2, i});
47            }
48        }
49        return result;
50    }
51}
52
1#include <vector>
2#include <string>
3#include <utility>
4
5using namespace std;
6
7// Define 'pii' as an alias for 'pair<int, int>'.
8using pii = pair<int, int>;
9
10class Solution {
11public:
12    // Main function to determine if one string can transition to another.
13    bool canChange(string start, string target) {
14        // Extract the positions and directions of 'L' and 'R' from both strings.
15        auto startPositions = extractPositions(start);
16        auto targetPositions = extractPositions(target);
17      
18        // If the number of 'L' and 'R' characters are different, return false.
19        if (startPositions.size() != targetPositions.size()) return false;
20      
21        // Check each corresponding 'L' and 'R' character from start and target.
22        for (int i = 0; i < startPositions.size(); ++i) {
23            auto startPosition = startPositions[i], targetPosition = targetPositions[i];
24            // If the direction is different, the change is not possible.
25            if (startPosition.first != targetPosition.first) return false;
26            // If an 'L' in start is to the right of the 'L' in target, change is not possible.
27            if (startPosition.first == 1 && startPosition.second < targetPosition.second) return false;
28            // If an 'R' in start is to the left of the 'R' in target, change is not possible.
29            if (startPosition.first == 2 && startPosition.second > targetPosition.second) return false;
30        }
31      
32        // If all 'L' and 'R' can be moved to their target positions, return true.
33        return true;
34    }
35
36    // Helper function to extract the positions and directions of 'L' and 'R'.
37    vector<pii> extractPositions(string s) {
38        vector<pii> positions;
39        for (int i = 0; i < s.size(); ++i) {
40            // If the character is 'L', associate it with direction 1.
41            if (s[i] == 'L')
42                positions.push_back({1, i});
43            // If the character is 'R', associate it with direction 2.
44            else if (s[i] == 'R')
45                positions.push_back({2, i});
46        }
47        return positions;
48    }
49};
50
1function canChange(start: string, target: string): boolean {
2    const length = start.length; // The length of the start and target strings
3    let startIdx = 0; // Start index for iterating through the start string
4    let targetIdx = 0; // Start index for iterating through the target string
5
6    while (true) {
7        // Skip all the underscores in the start string
8        while (startIdx < length && start[startIdx] === '_') {
9            ++startIdx;
10        }
11        // Skip all the underscores in the target string
12        while (targetIdx < length && target[targetIdx] === '_') {
13            ++targetIdx;
14        }
15
16        // If both indices have reached the end, the strings can be changed to each other
17        if (startIdx === length && targetIdx === length) {
18            return true;
19        }
20
21        // If one index reaches the end before the other, or the characters at the current indices do not match, 
22        // the strings cannot be changed to each other
23        if (startIdx === length || targetIdx === length || start[startIdx] !== target[targetIdx]) {
24            return false;
25        }
26
27        // If the character is 'L' and the start index is ahead of the target index, or 
28        // if the character is 'R' and the start index is behind the target index,
29        // it's not possible to change the strings according to the rules
30        if ((start[startIdx] === 'L' && startIdx < targetIdx) || (start[startIdx] === 'R' && startIdx > targetIdx)) {
31            return false;
32        }
33
34        // Move both indices forward
35        ++startIdx;
36        ++targetIdx;
37    }
38}
39

Time and Space Complexity

Time Complexity

The given Python function canChange checks whether it is possible to transform the start string into the target string under certain conditions. Analyzing the time complexity involves a few steps:

  1. Creation of list a: The list comprehension iterates over each character in the start string and includes only non-underscore characters. Therefore, this operation has a time complexity of O(n) where n is the length of the start string.

  2. Creation of list b: Similarly, the creation of list b iterates over each character in the target string and has a time complexity of O(n).

  3. Comparison of lengths: Checking if len(a) is equal to len(b) takes constant time, O(1).

  4. Zipping and iterating: Zipping the two lists a and b and iterating over them to compare elements has a time complexity of O(m), where m is the number of non-underscore characters in the strings, which is at most n.

Given these steps occur sequentially, the overall time complexity is dominated by the terms with O(n), leading to a total time complexity of O(n).

Space Complexity

  1. List a and b store the non-underscore characters and their respective indices from start and target. These take space proportional to the number of non-underscore characters, which is O(m) where m is the number of such characters.

  2. The space taken by the zip object and iteration is negligible since they don't store values but only reference the elements in a and b.

Hence, the overall space complexity of the function canChange is O(m), where m is the number of non-underscore characters and m <= n. If we consider that all characters could be non-underscore, the space complexity would also be O(n) in the worst case.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which type of traversal does breadth first search do?


Recommended Readings