LeetCode 1358. Number of Substrings Containing All Three Characters

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.size();
        function<int(int)> count = [&](int lower) {
            int freq[3] = {0}, res = 0;
            for (int left = 0, right = 0, cnt = 0; right < n; ++right) {
                if (++freq[s[right] - 'a'] == 1) ++cnt;
                while (cnt > lower)
                    if (--freq[s[left++] - 'a'] == 0) --cnt;
                res += right - left + 1;
            }
            return res;
        };
        return count(3) - count(2);
    }
};