难度: Medium
给你一个字符串 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^4s 只包含字符 a，b 和 c 。运行时间: 77 ms
内存: 16.2 MB
class Solution:
def numberOfSubstrings(self, s: str) -> int:
# 滑动窗口
n = len(s)
left = 0
ans = 0
cnt = defaultdict(int)
for right, ch in enumerate(s):
cnt[ch] += 1
while len(cnt) >= 3: # 表示区间内已经有a，b，c
ans += n - right
cnt[s[left]] -= 1
if cnt[s[left]] == 0:
del cnt[s[left]]
left += 1
return ans
class Solution:
def numberOfSubstrings(self, s: str) -> int:
N = len(s)
left = -1 # 窗口左侧坐标
a, b, c = -1, -1, -1 # 当前最近的a,b,c坐标
ans = 0
for right, ch in enumerate(s):
# 更新最近的a,b,c坐标
if ch == "a":
a = right
elif ch == "b":
b = right
else:
c = right
# 判断窗口内是否包含三个字母
if a > left and b > left and c > left:
new_left = min(a, b, c)
ans += (new_left - left) * (N - right)
left = new_left
return ans
这个题解使用了滑动窗口的方法来解决问题。维护一个动态的窗口[left, right]，该窗口内包含字符串s的所有字符a、b、c至少各一次。对于每个右端点right，通过不断扩展直到窗口包含所有三个字符。一旦窗口有效，即包含a、b、c三个字符，计算可以从当前窗口形成的有效子字符串的数量。随后逐渐移动左端点left直到窗口不再有效，每次移动更新答案。通过这种方法，可以有效地找到所有包含a、b、c的子字符串数量。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def numberOfSubstrings(self, s: str) -> int:
n = len(s) # 字符串的长度
left = 0 # 窗口的左边界
ans = 0 # 用于计数满足条件的子字符串数量
cnt = defaultdict(int) # 字典用于计数a, b, c的出现次数
for right, ch in enumerate(s): # 遍历字符串
cnt[ch] += 1 # 增加当前字符的计数
while len(cnt) >= 3: # 当窗口包含所有三种字符时
ans += n - right # 计算从当前窗口扩展出的所有有效子字符串的数量
cnt[s[left]] -= 1 # 减少左边界字符的计数
if cnt[s[left]] == 0: # 如果某字符计数为0，则从字典中移除
del cnt[s[left]]
left += 1 # 移动左边界
return ans # 返回结果
在题解中，每当右指针`right`向右移动并使得窗口包含所有三种字符时（a, b, c），从当前位置`right`向右的任何字符串都可以与窗口[left, right]结合形成一个有效的子字符串。因此，从`right`到字符串末尾（位置`n-1`）的子字符串数量是`n - right`。这是因为对于每个`right`位置，可以选择子字符串的结束位置在`right`到`n-1`之间的任何位置，因此组合数是`n-right`。
在题解中选择使用哈希表（这里使用的是`defaultdict(int)`）来存储窗口内各字符的出现次数，是因为哈希表能够快速地访问和更新元素。特别是在字符集未知或者字符种类较多时，哈希表能够有效地处理动态的字符集。相比之下，使用数组或计数器虽然也可行，但在字符集较大或者不固定时，哈希表的灵活性和扩展性更优。
是的，根据题解的逻辑，只有当窗口内包含所有三种字符时，才会开始检查并调整左指针`left`。这意味着在窗口不包含全部三种字符之前，右指针`right`会一直向右移动，直到窗口内至少包含了每种字符至少一次。这样做是为了确保窗口内始终是一个有效的包含所有三种字符的子串范围。
从字典中删除计数为0的字符主要是为了保持哈希表的大小尽可能小，这有助于减少内存使用，并且可以简化对窗口内是否包含所有必要字符的检查（通过查看哈希表的键的数量）。当字典中的键数量小于三时，可以快速判断窗口不包含所有三种字符，从而优化性能。此外，这种做法还避免了哈希表中积累无用的键值对，提高了算法的整体效率和执行速度。