Find an Replace in String

Given a string S on which you need to perform Q replace operations.
Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y. The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y. If not, we do nothing.

Note: All these operations occur simultaneously. It’s guaranteed that there won’t be any overlap in replacement: for example, S = “abc”, indexes = [0,1], sources = [“ab”, “bc”] is not a valid test case.

• Time : O(qlogq + n) in avg O(qlogq + n^2) in worst
• Space : O(q)

struct Query {
    int index;
    string source;
    string target;
};

class Solution {
    bool equal(string& s, int pos, string& t) {
        int i = 0;
        for(; pos < s.length() and i < t.length(); i++, pos++) {
            if(s[pos] != t[i]) return false;
        }
        
        return pos <= s.length() and i == t.length();
    }
public:
    string findAndReplace(string S ,int Q, int index[], string sources[], string targets[]) {
        string res = "";
        vector<Query> q;
        for(int i = 0; i < Q; i++)
            q.push_back({index[i], sources[i], targets[i]});
        
        sort(begin(q), end(q), [](Query& q1, Query& q2) {
            return q1.index < q2.index;
        });
        
        for(int i = 0, j = 0; i < S.length(); i++) {
            if(j >= q.size()) res.push_back(S[i]);
            else if(q[j].index != i) res.push_back(S[i]);
            else {
                if(equal(S, i, q[j].source)) {
                    res += q[j].target;
                    i += q[j].source.length() - 1;
                } else res.push_back(S[i]);
                j++;
            }
        }
        
        return res;
    }