包含所有三种字符的子字符串数目Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个字符串 s ，它只包含三种字符 a, b 和 c 。
请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。
示例 1：
输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。
示例 2：
输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。
示例 3：
输入：s = "abc"
输出：1
提示：
- 3 <= s.length <= 5 x 10^4
- s 只包含字符 a，b 和 c 。
# 思路
滑动窗口
# 解法
class Solution {
public int numberOfSubstrings(String s) {
char[] c = s.toCharArray(); // 将字符串转化为字符数组
int[] count = new int['d']; // 计数数组，只关心'a','b','c'的出现次数
int left = 0, ans = 0; // left为滑动窗口的左边界，ans为答案
// right为滑动窗口的右边界
for (int right = 0; right < c.length; right++) {
count[c[right]]++; // 将右边界的字符纳入计数
// 当窗口包含所有'a','b','c'时，尝试缩小窗口大小
while (count['a'] > 0 && count['b'] > 0 && count['c'] > 0) {
count[c[left++]]--; // 移动窗口左边界，减少该字符的计数
}
// 所有从0到left-1开始，到right结束的子串都是有效的
ans += left;
}
return ans; // 返回有效子串的数量
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 总结
- 分析出几种情况，然后分别对各个情况实现
