O(n)
We expand the sliding window, maintaining the count of each character in cnt.\n\nWhen we cnt[ch] becomes k, we increase the number of "k+" characters ch_k.\n\nW
We expand the sliding window, maintaining the count of each character in `cnt`.\n\nWhen we `cnt[ch]` becomes `k`, we increase the number of "k+" characters `ch_k`.\n\nWhen `ch_k` is positive, we find `len(s) - i` substrings.\n\nWe then shrink our window until `ch_k` becomes zero.\n\n**C++**\n```cpp\nint numberOfSubstrings(string s, int k) {\n    int cnt[26] = {}, ch_k = 0, res = 0, j = 0;\n    for (int i = 0; i < s.size(); ++i) {\n        ch_k += ++cnt[s[i] - \'a\'] == k;\n        for (; ch_k; ++j) {\n            res += s.size() - i;\n            ch_k -= cnt[s[j] - \'a\']-- == k;\n        }\n    }\n    return res;\n}\n```
['C']