2213. Longest Substring of One Repeating Character

You are given a 0-indexed string s. You are also given a 0-indexed string queryCharacters of length k and a 0-indexed array of integer indices queryIndices of length k, both of which are used to describe k queries.

The ith query updates the character in s at index queryIndices[i] to the character queryCharacters[i].

Return an array lengths of length k where lengths[i] is the length of the longest substring of s consisting of only one repeating character after the ith query is performed.

c++

class Solution {
    vector<map<int,int>> range;
    pair<int,int> editRange(char from, char to, int pos, bool front, bool back) {
        int prv = removeRange(from, pos);
        if(front and !back) {
            return {prv, mergeFront(to,pos)};
        }
        else if(!front and back) {
            return {prv, mergeBack(to,pos)};
        }
        else if(front and back) {
            return {prv, merge(to,pos)};
        }
        else {
            range[to-'a'][pos] = pos;
            return {prv, 1};
        }
    }
    int mergeFront(char to, int pos) {
        auto it = prev(range[to-'a'].upper_bound(pos));
        it->second = pos;
        return it->second - it->first + 1;
    }
    int mergeBack(char to, int pos) {
        auto it = range[to-'a'].upper_bound(pos);
        range[to-'a'][pos] = it->second;
        int f = pos, t = it->second;
        range[to-'a'].erase(it);
        return t - f + 1;
    }
    int merge(char to, int pos) {
        auto it = range[to-'a'].upper_bound(pos);
        auto prv = prev(it);
        prv->second = it->second;
        range[to-'a'].erase(it);
        return prv->second - prv->first + 1;
    }
    int removeRange(char from, int pos) {
        auto it = range[from-'a'].upper_bound(pos);
        it--;
        int prvrange = it->second - it->first + 1;
        if(it->second == pos) {
            if(it->first == pos)
                range[from-'a'].erase(it);
            else {
                it->second = pos - 1;
            }
        }
        else if(it->first == pos) {
            range[from-'a'][pos + 1] = it->second;
            range[from-'a'].erase(it);
        } else {
            range[from-'a'][pos + 1] = it->second;
            it->second = pos - 1;
        }
        return prvrange;
    }
    int getMaxLen() {
        int len = 0;
        for(int i = 0; i < 26; i++)
            for(auto [f, t]: range[i])
                len = max(len, t - f + 1);
        return len;
    }

public:
    vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
        range = vector<map<int,int>>(26);
        vector<int> res;
        int l = 0, r = 0, n = s.length();
        while(r < n) {
            while(r < n and s[r] == s[l]) r++;
            range[s[l]-'a'][l] = r - 1;
            l = r;
        }
        for(int i = 0; i < queryIndices.size(); i++) {
            if(s[queryIndices[i]] == queryCharacters[i] and !res.empty()) res.push_back(res.back());
            else {
                if(s[queryIndices[i]] != queryCharacters[i]) {
                    auto [pr, merged] = editRange(s[queryIndices[i]], queryCharacters[i], queryIndices[i], queryIndices[i] > 0 and s[queryIndices[i] - 1] == queryCharacters[i], queryIndices[i] + 1 < n and s[queryIndices[i] + 1] == queryCharacters[i]);
                    s[queryIndices[i]] = queryCharacters[i];
                    if(res.empty() or pr == res.back())
                        res.push_back(getMaxLen());
                    else if(merged >= res.back()) {
                        res.push_back(merged);
                    } else
                        res.push_back(res.back());
                } else 
                    res.push_back(getMaxLen());
            }
        }
        return res;
    }
};