Double Pointers - Question 2

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.

Constraints:

n == start.length == target.length

1 <= n <= 10^5

start and target consist of the characters 'L', 'R', and '_'.

Analysis:

The n could be pretty large, so we need to find an algorithm either O(N) or O(Nlog(N)).

Some key observations:

1. the number of L should be the same;

2. the number of R should be the same;

3. the corresponding index of L of start should always be larger or equal to that in target;

4. the corresponding index of L of start should always be smaller or equal to that in target.

For 3 & 4 above, we can consider to use the two-pointer method: one for the start string, and the other for the target.

For each of them, we can just scan if the char is '_';

Once find non '_' char, both should be same (o/w, just return false);

If it is the 'L' char, then if the first index p1 < p2, return false;

If it is the 'R' char, then if p1 > p2, return false.

If can finish the loop, return true.

The time complexity is O(N), and the space complexity is O(1).

See the code below:

class Solution {
public:
    bool canChange(string start, string target) {
        int n = start.size(), i = 0, j = 0;
        while(i < n || j < n) {
            while(i < n && start[i] == '_') ++i;
            while(j < n && target[j] == '_') ++j;
            if(i == n) return j == n;
            if(j == n) return i == n;
            if(start[i] != target[j]) return false;
            if(start[i] == 'L' && i < j) return false;
            if(start[i] == 'R' && i > j) return false;
            ++i;
            ++j;
        }
        return true;
    }
};

Upper Layer