Count Unique Characters of All Substrings of a Given String LeetCode solution in C++

1
class Solution {
2
 public:
3
  int uniqueLetterString(string s) {
4
    vector<vector<int>> counting(26);
5
    int ans = 0;
6

7
    // step 1: record the position for each char;
8
    for (int curr = 0; curr < 26; curr++) {
9
      counting[curr].push_back(-1);
10
    }
11

12
    for (int curr = 0; curr < s.size(); curr++) {
13
      counting[s[curr] - 'A'].push_back(curr);
14
    }
15

16
    for (int curr = 0; curr < 26; curr++) {
17
      counting[curr].push_back(s.size());
18
    }
19

20
    // step 2: for each char in s, find the # of contrubution for substring;
21
    for (int curr = 0; curr < 26; curr++) {
22
      for (int pos = 1; pos < counting[curr].size() - 1; pos++) {
23
        ans += (counting[curr][pos] - counting[curr][pos - 1]) *
24
               (counting[curr][pos + 1] - counting[curr][pos]);
25
      }
26
    }
27

28
    return ans;
29
  }
30
};