2337. Move Pieces to Obtain a String

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 '_'.

Approach 01:

class Solution {
public:
    bool canChange(string start, string target) {
        const int length = start.length();
        int startIndex = 0;  // Index for the start string
        int targetIndex = 0; // Index for the target string

        while (startIndex <= length && targetIndex <= length) {
            while (startIndex < length && start[startIndex] == '_')
                ++startIndex;
            while (targetIndex < length && target[targetIndex] == '_')
                ++targetIndex;

            if (startIndex == length || targetIndex == length)
                return startIndex == length && targetIndex == length;

            if (start[startIndex] != target[targetIndex])
                return false;

            if (start[startIndex] == 'R' && startIndex > targetIndex)
                return false;

            if (start[startIndex] == 'L' && startIndex < targetIndex)
                return false;

            ++startIndex;
            ++targetIndex;
        }

        return true;
    }
};

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        length = len(start)
        startIndex = 0  # Index for the start string
        targetIndex = 0  # Index for the target string

        while startIndex <= length and targetIndex <= length:
            while startIndex < length and start[startIndex] == '_':
                startIndex += 1
            while targetIndex < length and target[targetIndex] == '_':
                targetIndex += 1

            if startIndex == length or targetIndex == length:
                return startIndex == length and targetIndex == length

            if start[startIndex] != target[targetIndex]:
                return False

            if start[startIndex] == 'R' and startIndex > targetIndex:
                return False

            if start[startIndex] == 'L' and startIndex < targetIndex:
                return False

            startIndex += 1
            targetIndex += 1

        return True

Time Complexity

• Traversing the strings:

  The function uses two pointers, startIndex and targetIndex, to traverse the strings start and target. Each character is processed at most once, so the traversal takes \(O(N)\), where \(N\) is the length of the strings.

• Skipping underscores:

  The while loops used to skip underscores are also linear in nature and contribute to \(O(N)\).

• Overall Time Complexity:

  The overall time complexity is \(O(N)\), as all operations are linear with respect to the string length.

Space Complexity

• Auxiliary variables:

  The function uses two integer variables, startIndex and targetIndex, for pointer traversal. These require \(O(1)\) space.

• Input strings:

  The input strings start and target are passed as references and do not contribute to additional space usage.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as no additional data structures are used.