包含所有三种字符的子字符串数目

滑动窗口 ，直接统计合法子串用滑动窗口维护[left, right]区间，保证区间内包含所有字符，当窗口满足条件时，所有以right为结尾、以[0, left-1]为起点的子串都合法，数量为left； 移动左指针缩小窗口，继续统计。

class Solution {
public:
    int numberOfSubstrings(string s) {
        int ans = 0, left = 0;
        unordered_map<int, int> cnt; // 统计a、b、c的出现次数
        
        for (char c : s) {
            cnt[c - 'a']++; // 右指针右移，统计当前字符
            
            // 窗口包含所有字符时，缩小左边界
            while (cnt[0] && cnt[1] && cnt[2]) {
                cnt[s[left] - 'a']--;
                left++;
            }

            ans += left;
        }
        return ans;
    }
};

时间复杂度 O(n)