1358.md

title	description	keywords
1358. 包含所有三种字符的子字符串数目	LeetCode 1358. 包含所有三种字符的子字符串数目题解，Number of Substrings Containing All Three Characters，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1358. 包含所有三种字符的子字符串数目 包含所有三种字符的子字符串数目 Number of Substrings Containing All Three Characters 解题思路 哈希表 字符串 滑动窗口

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	统计完全子字符串		哈希表 字符串 滑动窗口	🔴	🀄️ 🔗