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

🎯 问题描述（来源于LeetCode）

描述：
给定一个由字符 'a'、'b'、'c' 组成的字符串 s。请返回包含至少一个 'a'、一个 'b' 和一个 'c' 的子字符串数量。

说明：

  • 子字符串是连续的。
  • s 的长度在 [3, 5×10^4] 之间。

示例：

  • 示例 1：
1
2
3
输入: s = "abcabc"
输出: 10
解释: 包含 a,b,c 的子串共有 10 个。
  • 示例 2：
1
2
输入: s = "aaacb"
输出: 3

💻 解题思路

思路：滑动窗口（双指针）

算法步骤

  1. 将字符串转为字符列表（或直接迭代字符串）。
  2. 初始化左指针 left = 0，计数器 count = {'a':0, 'b':0, 'c':0}，答案 ans = 0。
  3. 遍历右指针 right，将当前字符 s[right] 加入计数。
  4. 当窗口中同时包含至少一个 'a'、'b'、'c' 时，说明以当前左指针为起点、右指针为终点以及更右的终点，所有子串都满足条件。此时，left 表示最小的合法左端点，因此以 left 及更小的左端点（即 0 到 left-1）作为起点的子串也都满足条件，数量为 left + 1（即 left 本身？代码中 ans += left 实际上累加了 left 的值，但通常应为 left + 1。需要确认代码正确性：标准做法是 ans += left + 1。但用户代码写的是 ans += left。我们需在思考中解释。）
  5. 然后移动左指针，尝试收缩窗口，并更新计数，直到窗口不再满足条件。
  6. 返回 ans。

代码实现（您的代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        st = [c for c in s]
        left = 0
        ans = 0
        count = {"a": 0, "b": 0, "c": 0}
        for right, ch in enumerate(st):
            count[ch] += 1
            while count["a"] * count["b"] * count["c"] != 0:
                ch = st[left]
                count[ch] -= 1
                left += 1
            ans += left
        return ans

📊 性能分析

  • 时间复杂度：O(n)O(n)，每个元素最多被左右指针各访问一次。
  • 空间复杂度：O(1)O(1)，使用固定大小的字典。

思考

该解法利用滑动窗口统计所有满足条件的子串。当窗口内包含 a、b、c 至少各一个时，若左指针为 left，则以当前右端点 right 为结尾的子串中，左端点可以是 0 到 left-1 中的任意一个（因为这些子串也必然包含全部三种字符，因为它们包含当前窗口的左半部分），共 left 个。因此将 left 累加到答案中，而不是 left+1，是因为左端点取 0 到 left-1 共 left 种。这正是代码 ans += left 的原因。在每次满足条件并收缩后，left 已经是第一个使得窗口不满足条件的左端点，所以以 right 为结尾的合法子串数为 left。
注意：若左指针从 0 开始，当第一次满足条件时，left 可能为 1（因为收缩一次），此时 ans += 1，代表以 right 为结尾且左端点为 0 的子串合法，数量为 1，正确。该算法是此题的高效解法，代码简洁，但在理解上需要留意累加逻辑。