Maximum Number of Non-Overlapping Substrings LeetCode solution in C++

1
class Solution {
2
 public:
3
  void rangeOfChar(pair<int, int> startEnd[], string s, int visited[]) {
4
    int n = s.length();
5

6
    for (int i = n - 1; i >= 0; i--) {
7
      auto asciiInd = s[i] - 'a';
8
      auto rangeInd = startEnd[asciiInd];
9
      visited[asciiInd] = i;
10
      if (rangeInd.first == i) {
11
        for (int j = 0; j < 26; j++) {
12
          auto rangeLookup = startEnd[j];
13
          if (rangeLookup.first != -1 && rangeLookup.first <= i &&
14
              rangeLookup.second >= rangeInd.first && rangeInd.second >= rangeLookup.second) {
15
            rangeInd.first = min(rangeLookup.first, rangeInd.first);
16
            rangeInd.second = max(rangeLookup.second, rangeInd.second);
17
          } else if (visited[j] != -1 && visited[j] < rangeInd.second) {
18
            rangeInd.first = min(rangeLookup.first, rangeInd.first);
19
            rangeInd.second = max(rangeLookup.second, rangeInd.second);
20
          }
21
        }
22
      }
23

24
      startEnd[asciiInd] = rangeInd;
25
    }
26
  }
27

28
  vector<string> maxNumOfSubstrings(string s) {
29
    pair<int, int> startEnd[26];
30
    for (int i = 0; i < 26; i++) startEnd[i] = {-1, -1};
31
    int visited[26];
32
    memset(visited, -1, sizeof(visited));
33
    int n = s.length();
34
    vector<string> ans;
35

36
    for (int i = 0; i < n; i++) {
37
      int charIndex = s[i] - 'a';
38
      if (startEnd[charIndex].first == -1) {
39
        startEnd[charIndex].first = i;
40
      }
41
      startEnd[charIndex].second = i;
42
    }
43

44
    rangeOfChar(startEnd, s, visited);
45

46
    int lastIndex = -1;
47

48
    for (int i = 0; i < n; i++) {
49
      if (startEnd[s[i] - 'a'].first < i) continue;
50
      auto range = startEnd[s[i] - 'a'];
51
      // cout<<range.first<<" "<<range.second<<" "<<s[i]<<endl;
52
      if (range.first == -1) continue;
53
      if (range.second < lastIndex) {
54
        ans.pop_back();
55
      }
56
      lastIndex = range.second;
57
      ans.push_back(s.substr(range.first, range.second - range.first + 1));
58
    }
59

60
    return ans;
61
  }
62
};