1358：包含所有三种字符的子字符串数目（1646 分）

力扣第 20 场双周赛第 3 题

题目

给你一个字符串 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 。

分析

子字符串的总数很好求，因此可以反过来求不同时包含 a、b、c 的子字符串个数。这即是典型的滑动窗口问题。

解答

1
2
3
4
5
6
7
8
9

def numberOfSubstrings(self, s: str) -> int:
	res,i,ct = 0,0,Counter()
	for j,c in enumerate(s):
		ct[c] += 1
		while ct['a'] and ct['b'] and ct['c']:
			ct[s[i]] -= 1
			i += 1
		res += i
	return res

212 ms