LeetCode 2213. Longest Substring of One Repeating Character

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
        int n = s.size(), k = queryCharacters.size();
        map<int, int> m; // {{left, right}}
        multiset<int> ms; // {length}
        for (int i = 0; i < n;) {
            int j = i + 1;
            while (j < n && s[j] == s[i]) ++j;
            m[i] = j - 1;
            ms.insert(j - i);
            i = j;
        }
        // cut from pos `left` if `left` is not a start of certain range.
        auto cut = [&](int left)-> void {
            if (left < 0 || left >= n) return;
            if (!m.count(left)) {
                // get the range that contains `left`.
                auto [l, r] = *prev(m.lower_bound(left));
                ms.extract(r - l + 1);
                // split into two ranges, [l, left - 1], [left, r].
                m[l] = left - 1;
                m[left] = r;
                ms.insert(left - l);
                ms.insert(r - left + 1);
            }
        };
        // join the range that starts with `left` with its prev range if possible.
        auto join = [&](int left) -> void {
            if (left <= 0 || left >= n) return;
            auto [pl, pr] = *prev(m.lower_bound(left));
            if (s[pl] == s[left]) {
                ms.extract(pr - pl + 1);
                ms.extract(m[left] - left + 1);
                ms.insert(m[left] - pl + 1);
                m[pl] = m[left];
                m.erase(left);
            }
        };
        vector<int> ans(k);
        for (int i = 0; i < k; ++i) {
            int left = queryIndices[i];
            char ch = queryCharacters[i];
            if (s[left] != ch) {
                s[left] = ch;
                cut(left), cut(left + 1);
                join(left), join(left + 1);
            }
            ans[i] = *ms.rbegin();
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    string s;
    struct Node {
        int l, r, prefix, suffix, val;
        Node() {}
        Node(int l, int r) : l(l), r(r), prefix(1), suffix(1), val(1) {}
    } tr[400000];
    void build(int u, int l, int r) {
        tr[u] = {l, r};
        if (l == r) return;
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
    void update(int u, int i, char c) {
        if (tr[u].l == i && tr[u].r == i) {
            s[i - 1] = c;
            return;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        if (i <= mid) update(u << 1, i, c);
        else update(u << 1 | 1, i, c);
        pushup(u);
    }
    void pushup(int u) {
        auto left = tr[u << 1], right = tr[u << 1 | 1];
        int leftLen = left.r - left.l + 1, rightLen = right.r - right.l + 1;
        char leftLast = s[left.r - 1], rightFirst = s[right.l - 1];
        tr[u].prefix = left.prefix, tr[u].suffix = right.suffix, tr[u].val = max(left.val, right.val);
        if (leftLast == rightFirst) {
            if (left.prefix == leftLen) tr[u].prefix = leftLen + right.prefix;
            if (right.prefix == rightLen) tr[u].suffix = left.suffix + rightLen;
            tr[u].val = max(tr[u].val, left.suffix + right.prefix);
        }
    }
    int query(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
        int ans = 0, mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) ans = query(u << 1, l, r);
        if (r > mid) ans = max(ans, query(u << 1 | 1, l, r));
        return ans;
    }
    vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
        int n = s.size(), k = queryIndices.size();
        this->s = s;
        build(1, 1, n);
        for (int i = 0; i < n; ++i) update(1, i + 1, s[i]);
        vector<int> ans(k);
        for (int i = 0; i < k; ++i) {
            update(1, queryIndices[i] + 1, queryCharacters[i]);
            ans[i] = query(1, 1, n);
        }
        return ans;
    }
};