Move Pieces to Obtain a String

Leetcode Problem:

• Move Pieces to Obtain a String

Summary

• Check if a string can be transformed into another string by moving pieces (L, R, _) a certain number of times.

Approach

• This solution uses a two-pointer approach to iterate over both strings simultaneously
• It checks for the next available position for each piece in both strings and moves them accordingly
• If a piece cannot be moved to its next position, it returns false
• If all pieces can be moved to their next positions, it checks if both strings have been fully traversed and returns true if so, otherwise false.

Complexity

• O(n), where n is the length of the input strings.

Explanation

• The solution defines two helper functions, `nextCharIdx`, to find the next available position for each piece in both strings
• It then iterates over both strings using two pointers, `idx1` and `idx2`, which start at the beginning of each string
• It checks if the current positions in both strings match, and if they do, it moves the pieces to the next position
• If a piece cannot be moved to its next position, it returns false
• If all pieces can be moved to their next positions, it checks if both strings have been fully traversed and returns true if so, otherwise false.

Solution Code:

class Solution {
public:
    int nextCharIdx(string& str, int idx){
        for(int i = idx; i < str.size(); i++){
            if(str[i] == 'L' || str[i] == 'R') return i;
        }
        return str.size();
    }
    bool canChange(string start, string target) {
        int idx1, idx2;
        idx1 = idx2 = 0;
        while(true){
            idx1 = nextCharIdx(start, idx1);
            idx2 = nextCharIdx(target, idx2);
            if(idx1 == start.size() || idx2 == target.size()){       
                break;
            }
            if(start[idx1] != target[idx2]) return false;
            if(start[idx1] == 'L'){
                if(idx1 < idx2){
                    return false;
                }
            }
            if(start[idx1] == 'R'){
                if(idx1 > idx2){
                    return false;
                }
            }
            idx1++;
            idx2++;
        }
        if(idx1 == start.size() && idx2 == target.size()){
            return true;
        }
        return false;
    }
};