Longest Substring of One Repeating Character LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> longestRepeating(string s, string queryCharacters, vector<int> &queryIndices) {
4
    multiset<int> ls; // ordered set of lengths of all intervals at present
5
    set<int> ins;     // ordered set representing the left-ends of intervals
6
    int n = s.length();
7
    ins.insert(n); // allow us to get length of current interval by *next(it) -
8
                   // *it for all cases
9

10
    // initialize the ordered sets with the original string
11
    for (int i = 0, j = 1; i < n;) {
12
      while (j < n && s[j] == s[j - 1]) ++j;
13
      ins.insert(i);
14
      ls.insert(j - i);
15
      i = j++;
16
    }
17

18
    // update the string and track the length of the longest substring
19
    // by merging/splitting intervals
20
    vector<int> ans;
21
    for (int i = 0; i < queryIndices.size(); ++i) {
22
      // If the querying character does not change the string:
23
      // do nothing for the sets
24
      if (queryCharacters[i] == s[queryIndices[i]]) {
25
        ans.push_back(*ls.rbegin());
26
        continue;
27
      }
28

29
      // update the ordered sets
30
      // 1. split the involved interval to parts: (left), self, (right)
31
      // ins = 0 3 6
32
      // s = b b b c c c
33
      // query : b
34
      // => ins = 0 3 4 6
35
      // => s = b b b b c c
36

37
      // find the left-end of the target interval
38
      auto it = prev(ins.upper_bound(queryIndices[i])); // old/left interval
39
      int oldl = *next(it) - *it;                       // old interval length
40
      ls.erase(ls.find(oldl));
41

42
      ins.insert(queryIndices[i]);                                  // self interval
43
      ins.insert(queryIndices[i] + 1);                              // right interval
44
      if (*it != queryIndices[i]) ls.insert(queryIndices[i] - *it); // left interval length
45
      ls.insert(1);                                                 // self interval length
46
      if (oldl - (queryIndices[i] - *it + 1))
47
        ls.insert(oldl - (queryIndices[i] - *it + 1)); // right interval length
48

49
      s[queryIndices[i]] = queryCharacters[i];
50

51
      // 2. merge the adjacent intervals if the characters are identical
52
      // ins = 0 3 4 6
53
      // s = b b b b c c
54
      // => ins = 0 4 6
55

56
      it = ins.find(queryIndices[i]); // self interval
57
      // merge self and right
58
      if (queryIndices[i] + 1 < n && s[queryIndices[i]] == s[queryIndices[i] + 1]) {
59
        ls.erase(ls.find(*next(it, 2) - *next(it)));
60
        ls.erase(ls.find(1));
61
        ins.erase(next(it));
62
        ls.insert(*next(it) - *it);
63
      }
64
      // merge left and self
65
      if (it != ins.begin() && s[queryIndices[i]] == s[queryIndices[i] - 1]) {
66
        ls.erase(ls.find(*next(it) - *it));
67
        ls.erase(ls.find(*it - *prev(it)));
68
        ls.insert(*next(it) - *prev(it));
69
        ins.erase(it);
70
      }
71
      ans.push_back(*ls.rbegin());
72
    }
73
    return ans;
74
  }
75
};