Unique Approach!! : Path Compression | TC: O(n) | SC: O(n) | Different approach from Editorial
IntuitionBasically, the problem can be re-defined as:
Each _ can shift a place with an L on its right. However, this operation is not possible if there is an R
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Basically, the problem can be re-defined as:
1. Each _ can shift a place with an L on its right. However, this operation is not possible if there is an R in between the _ and the L.
2. Each R can shift a place with an _ on its right. However, this operation is not possible if there is an L in between the R and the _.

Hence, traversing from left to right, we need to know, for each position, where is the next L located on the right, and when is the next _ located on the right. This we pre-compute and store in the arrays: next_l and next_uscore.



# Approach
<!-- Describe your approach to solving the problem. -->
- We traverse through the whole string, and check for the possibility of swaps when the individual strings do not match. If the swap is possible, we perform the operation. This, however, must change the next_l and next_uscore arrays. Hence, we do path compression so as to avoid redundant calculations (in locating the next_uscore or next_l at the required index).
- *This is worth noting that if the path compression is done recursively, it gives an "MLE" on 98th test case. Hence, the recursive stack needs to be voided, hence, the iterative path compression instead.*
# Complexity
- Time complexity: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
    vector<int> next_l, next_uscore;
    int find_next_l(string& start, int idx) {
        while (idx != -1 && start[idx] != 'L') {
            idx = next_l[idx];
        }
        return idx;
    }

    int find_next_uscore(string& start, int idx) {
        while (idx != -1 && start[idx] != '_') {
            idx = next_uscore[idx];
        }
        return idx;
    }
public:
    bool canChange(string start, string target) {
        int n1 = start.length(), n2 = target.length();
        int l1 = 0, l2 = 0;
        int l_idx = -1, uscore_idx = -1;
        next_uscore.resize(n1, -1);
        next_l.resize(n1,-1);
        for(int i=n1-1; i>=0; i--){
            next_l[i] = l_idx;
            next_uscore[i] = uscore_idx;
            if(start[i]=='L'){
                l_idx=i;
                uscore_idx = -1;
            }
            if(start[i]=='R'){
                l_idx=-1;
            }
            if(start[i]=='_'){
                uscore_idx = i;
            }
        }
        while(l1<n1 and l2<n2){
            if(start[l1]==target[l2]){
                l1++;
                l2++;
                continue;
            }
            if(start[l1]!='_' and target[l2]!='_'){
                // cout<<start;
                return false;
            }
            if(start[l1] == 'L' or target[l2]=='R'){
                // cout<<start<<" h1";
                return false;
            }
            if(start[l1]=='R' and target[l2]=='_'){
                int next_uscore_idx = find_next_uscore(start, l1);
                if(next_uscore_idx != -1){
                    swap(start[next_uscore_idx], start[l1]);
                    if(l1+1<n1 and next_uscore_idx != l1+1){
                        next_uscore[l1+1] = next_uscore_idx;
                    }
                    l1++; l2++;
                    continue;
                } else{
                    // cout<<start<<" h2 "<<l1;
                    return false;
                }
            }
            if(start[l1]=='_' and target[l2]=='L'){
                int next_l_idx = find_next_l(start, l1);
                if(next_l_idx == -1){
                    // cout<<start<< " h3";
                    return false;
                }
                swap(start[l1], start[next_l_idx]);
                if(l1+1<n1 and next_l_idx != l1+1){
                    next_l[l1+1] = next_l_idx;
                }
                l1++;
                l2++;
                continue;
            }
        }
        return true;
    }
};
```
['C++']