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

🟠 Medium  🔖  哈希表 字符串 滑动窗口  🔗 力扣 LeetCode

题目

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
• s only consists of a , b or c characters.

题目大意

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

解题思路

1. 使用 滑动窗口 (l 到 r) 遍历 s，并维护一个 固定大小的数组 count[3] 记录当前窗口内 a, b, c 出现的次数。

2. 右边界扩展窗口 (r 从 0 到 n-1)

   • count[s[r]] 计数 +1，表示字符 s[r] 进入窗口。

3. 左边界缩小窗口 (l++)

   • 当 count[0] > 0 && count[1] > 0 && count[2] > 0（即窗口内包含 a, b, c）时：
   • count[s[l]] 计数 -1，l++ 移动左边界。

4. 统计符合条件的子字符串

   • 缩小左边界直到窗口内不再同时包含 a, b, c，此时 l 代表有多少个可行的子字符串
   • result += l，计算所有可能的子字符串。

复杂度分析

• 时间复杂度：O(n)，遍历 s。
• 空间复杂度：O(1)，只是用了常数个变量。

代码

/**
 * @param {string} s
 * @return {number}
 */
var numberOfSubstrings = function (s) {
	let l = 0;
	let result = 0;
	let count = [0, 0, 0];
	for (let r = 0; r < s.length; r++) {
		count[s.charCodeAt(r) - 97]++;
		// 只有当 'a', 'b', 'c' 都出现后，才移动左指针
		while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
			count[s.charCodeAt(l) - 97]--;
			l++;
		}
		result += l;
	}
	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
2063	所有子字符串中的元音		数学 字符串 动态规划 1+	🟠	🀄️ 🔗
2953	统计完全子字符串		哈希表 字符串 滑动窗口	🔴	🀄️ 🔗