Given a string s consisting only of characters a, b and c.
Return the number of substrings containing at least one occurrence of all these characters a, b and c.
Example 1:
Input: s = "abcabc" Output: 10 Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).
Example 2:
Input: s = "aaacb" Output: 3 Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".
Example 3:
Input: s = "abc" Output: 1
Constraints:
3 <= s.length <= 5 x 10^4-
sonly consists of a, b or c characters.
包含所有三种字符的子字符串数目。
给你一个字符串 s ，它只包含三种字符 a, b 和 c 。请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。
思路是滑动窗口。这道题的窗口卡的是一个子区间满足子区间内unique key的个数是3。同时因为input里只有abc三个字母，所以当你找到第一个子串的终点 end 的时候，子串[start, s.length - 1] 其实都是满足题意的子串，所以此时可以尝试移动 start 指针，只有count == 3的时候，我们才能移动 start 指针。这道题依然可以使用76题的模板。
时间O(n)
空间O(1) - letter数组可以忽略不计
Java实现
1 class Solution {
2 public int numberOfSubstrings(String s) {
3 int len = s.length();
4 int[] letter = new int[3];
5 int count = 0;
6 int res = 0;
7 int start = 0;
8 int end = 0;
9 while (end < s.length()) {
10 char c1 = s.charAt(end);
11 if (letter[c1 - 'a']++ == 0) {
12 count++;
13 }
14 while (count == 3) {
15 res += len - end;
16 char c2 = s.charAt(start);
17 if (letter[c2 - 'a']-- == 1) {
18 count--;
19 }
20 start++;
21 }
22 end++;
23 }
24 return res;
25 }
26 }