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

---

C代码：滑动窗口、前缀

// 只存在abc
// 存在三种字符的子串数量、左边窗口满足，窗口后边的也就满足
int numberOfSubstrings(char * s){int hash[3] = {0};int n = strlen(s);int ans = 0;int l = 0;for (int i = -1; i < n;) { // 遍历窗口每一个起点，从每个起点开始往右伸展，直到构建完成一个窗口，再更新起点while(i < n && (hash[0] < 1 || hash[1] < 1 || hash[2] < 1)) {if (++i == n) {break;}hash[s[i] - 'a']++;  // aaacb 到b后，i为n-1，确保i<n还能进入循环}ans += n - i;  // aaacb aacb acbhash[s[l++] - 'a']--;  // 更新每一个窗口起点}return ans;
}

---

C代码：错误版本

// 只存在abc
// 存在三种字符的子串数量、左边窗口满足，窗口后边的也就满足
int numberOfSubstrings(char * s){int hash[3] = {0};int n = strlen(s);int ans = 0;int l = 0;for (int i = 0; i < n;) { // 遍历窗口每一个起点，从每个起点开始往右伸展while(i < n && (hash[0] < 1 || hash[1] < 1 || hash[2] < 1)) {hash[s[i++] - 'a']++;  // aaacb 到b后，i为n了，就不再进入循环}ans += n - i + 1;hash[s[l++] - 'a']--;}return ans;
}