LeetCode 题解工作台
包含所有三种字符的子字符串数目
给你一个字符串 s ，它只包含三种字符 a, b 和 c 。 请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。 示例 1： 输入： s = "abcabc" 输出： 10 解释： 包含 a，b 和 c 各至少一次的子字符串为 " abc ", " abca ", " abcab ", …
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 滑动窗口（状态滚动更新）
答案摘要
我们用一个长度为 的数组 记录三种字符最近一次出现的位置，初始时均为 。 遍历字符串 ，对于当前位置 ，我们先更新 ，然后合法的字符串个数为 $\min(d[0], d[1], d[2]) + 1$，累加到答案中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你一个字符串 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 。
解题思路
方法一：一次遍历
我们用一个长度为 的数组 记录三种字符最近一次出现的位置，初始时均为 。
遍历字符串 ，对于当前位置 ，我们先更新 ，然后合法的字符串个数为 ，累加到答案中。
时间复杂度 ，其中 为字符串 的长度。空间复杂度 。
class Solution:
def numberOfSubstrings(self, s: str) -> int:
d = {"a": -1, "b": -1, "c": -1}
ans = 0
for i, c in enumerate(s):
d[c] = i
ans += min(d["a"], d["b"], d["c"]) + 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because we scan the string once, updating last seen indices and computing the minimum each iteration. Space complexity is O(1) since we only store the latest positions of three characters, independent of string length. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Candidate identifies sliding window as the optimal approach instead of brute force substring checking.
- question_mark
Candidate demonstrates correct running state updates for each character and uses minimum index for counting.
- question_mark
Candidate maintains O(1) extra space and explains why checking all substrings is unnecessary.
常见陷阱
外企场景- error
Attempting to check every possible substring, resulting in O(n^2) time.
- error
Failing to update last seen indices correctly when characters repeat.
- error
Counting substrings incorrectly by not considering the minimum last seen position of all three characters.
进阶变体
外企场景- arrow_right_alt
Count substrings containing at least K distinct characters instead of exactly three specific ones.
- arrow_right_alt
Extend the problem to larger alphabets beyond 'a', 'b', 'c', requiring dynamic hash table updates.
- arrow_right_alt
Compute the longest substring containing all three characters rather than the total number of substrings.