力扣1358.包含所有三种字符的子字符串数目
力扣1358.包含所有三种字符的子字符串数目
遍历左端点 找到最小的子字符串
- res += n – j(右边全部)
class Solution { public: int numberOfSubstrings(string s) { unordered_map<char,int> cnt; int n = s.size(),res=0,count=3; for(int i=0,j=0;j<n;j++) { if(!cnt.count(s[j])) count--; cnt[s[j]] ++; while(!count) { res += n - j; if(--cnt[s[i]] == 0) { count++; cnt.erase(s[i]); } i++; } } return res; } };