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

2023-10-24 HGNULB 约 8 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

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

题意分析

给一个只由 a、b、c 三种字符组成的字符串，数一数其中有多少个子串同时包含这三种字符。子串是连续的一段，按起止位置区分，内容相同但位置不同也要分别计数。

字符集只有三种，这是最强的信号：判断一个窗口是否合格，只需要看三个计数是否都为正，一次比较就是常数时间，完全不必用哈希表或者集合。

「同时包含」是一个单调条件——一段区间合格的话，把它向左或向右延长仍然合格，因为原有字符一个都没少。这条单调性是后面所有优化的地基。

字符串长度可达 $5 \times 10^4$，子串总数是 $O(n^2)$ 级别（约 12 亿），逐个枚举并检查显然过不了，必须找到批量计数的办法。答案本身不超过 $n(n+1)/2 \approx 1.25 \times 10^9$，超过了 32 位有符号整数的一半但仍在范围内，Java 用 int 恰好安全。

解法：滑动窗口计数贡献

核心思路

暴力做法是双重循环枚举左右端点，再花 $O(1)$ 到 $O(n)$ 判断是否合格，总代价至少 $O(n^2)$，$n = 5 \times 10^4$ 时跑不完。

瓶颈在于「逐个数」这件事本身。既然合格性对区间延长是单调的，那么固定左端点 $l$ 之后，一定存在一个临界位置 $R(l)$：右端点取到 $R(l)$ 时窗口刚好凑齐三种字符，取更小则不够，取更大则依然合格。于是以 $l$ 开头的合格子串恰好有 $n - R(l)$ 个，一次就能算出一整批，不必逐个枚举右端。

更进一步，$R(l)$ 随 $l$ 增大而单调不减：左端右移只会让窗口内字符变少，凑齐所需的右边界只会更远。这正是双指针能成立的条件——左右指针都只向右走，总步数 $O(n)$。

代码用的是一个等价但更紧凑的组织方式：外层枚举右端 $right$ 逐个加入字符，内层 while 在窗口合格时不断做两件事——把当前左端 $left$ 的贡献 $n - right$ 计入答案，然后把 $left$ 移出窗口。这里的不变量是：每个左端点 $left$ 恰好在窗口首次对它合格的那一刻被结算一次，结算用的 $right$ 正是 $R(left)$。因为内层循环一旦发现合格就立刻结算并弹出左端，左端不会被结算第二次；而弹出后若仍合格，说明下一个左端的临界值也是当前 $right$，继续结算即可。

换句话说，答案被拆成了 $\sum_{l} (n - R(l))$，每一项在左指针经过时一次性加满。窗口状态只用三个计数维护，加入和移出都是 $O(1)$。

解题步骤

准备长度为 3 的计数数组 count、左指针 left = 0、答案 res = 0。用数组下标 c - 'a' 定位，比哈希表省掉哈希开销。

外层循环让 right 从 0 走到 $n-1$，每轮先把 s[right] 的计数加一，把它纳入窗口。先扩右再判定，保证判定时窗口是 $[left, right]$ 的真实状态。

内层 while 判断三个计数是否都大于 0。用 while 而非 if，是因为弹出一个左端字符后窗口可能仍然合格（比如该字符在窗口里有多份），此时下一个左端的临界右界同样是当前 right，必须继续结算。

每次满足条件就 res += n - right。这一项的含义是：以当前 left 为起点、以 right 到 $n-1$ 中任意位置为终点的子串全部合格，共 $n - right$ 个。加的是 $n - right$ 而不是 $right - left + 1$，因为批量方向是向右延伸而非向左。

结算完立刻把 s[left] 的计数减一并让 left++。先结算后弹出的顺序不能反，否则这个左端的贡献就丢了。

外层跑完返回 res。左右指针各自最多前进 $n$ 步，整体线性。

以 s = "abcabc" 走一遍（$n = 6$）：right = 0 加入 a，计数是 $(1,0,0)$，c 缺席，不结算。right = 1 加入 b，计数 $(1,1,0)$，仍缺 c。right = 2 加入 c，计数 $(1,1,1)$ 全部为正：结算 left = 0，res += 6 - 2 = 4（对应子串 abc、abca、abcab、abcabc），弹出 s[0] = a，计数变 $(0,1,1)$，left = 1，不再合格，退出内层。right = 3 加入 a，计数 $(1,1,1)$：结算 left = 1，res += 6 - 3 = 3，累计 7（新增以下标 1 开头的 bca、bcab、bcabc），弹出 s[1] = b，计数 $(1,0,1)$，left = 2。right = 4 加入 b，计数 $(1,1,1)$：结算 left = 2，res += 6 - 4 = 2，累计 9，弹出 s[2] = c，计数 $(1,1,0)$，left = 3。right = 5 加入 c，计数 $(1,1,1)$：结算 left = 3，res += 6 - 5 = 1，累计 10，弹出 s[3] = a，计数 $(0,1,1)$，left = 4。外层结束，返回 10。四个起点 0、1、2、3 各被结算一次，起点 4 和 5 后面的字符不足三种，一次都没被结算，正是应有的结果。

代码实现

class Solution {
    // 固定左端时不好直接数所有右端。
    public int numberOfSubstrings(String s) {
        int[] count = new int[3];
        int left = 0;
        int res = 0;

        for (int right = 0; right < s.length(); right++) {
            count[s.charAt(right) - 'a']++;

            while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
                res += s.length() - right;
                count[s.charAt(left) - 'a']--;
                left++;
            }
        }

        return res;
    }
}

func numberOfSubstrings(s string) int {
    // 固定左端时不好直接数所有右端。
    count := make([]int, 3)
    left := 0
    res := 0

    for right := 0; right < len(s); right++ {
        count[s[right]-'a']++

        for count[0] > 0 && count[1] > 0 && count[2] > 0 {
            res += len(s) - right
            count[s[left]-'a']--
            left++
        }
    }

    return res
}

复杂度分析

时间复杂度：$O(n)$，right 单调走完整个串，left 在所有内层循环中累计前进也不超过 $n$ 次，两个指针互不回退；窗口的加入、移出和合格判定都是常数时间。

空间复杂度：$O(1)$，只有长度为 3 的计数数组和几个标量，与串长无关。

关键点总结

「统计满足条件的子串数目」和「求满足条件的最长/最短子串」是两类题。前者要按贡献批量累加，后者只需在极值处更新，套错模板会从根上算错。

单调性是双指针的前提：本题的条件对区间延长封闭，所以临界右界 $R(l)$ 随 $l$ 单调不减，左右指针才能都只进不退。

贡献取 $n - right$ 而不是 $right - left + 1$，方向由「固定左端向右延伸」这个拆分方式决定。写之前先确认自己拆的是哪一维，能避免大多数计数偏差。

内层必须用 while：弹出一个字符后窗口可能仍合格，这时是下一个左端在同一个 right 处结算，用 if 会漏掉整批答案。

字符集固定为三种时，用长度为 3 的数组代替哈希表，常数小且不会有哈希碰撞开销；这个技巧在只含小写字母的题里同样适用。

面试视角：面试官通常会先追问「为什么两个指针都不回头」，再追问「换成必须包含 $k$ 种字符怎么改」。前者答单调性，后者答把三个计数换成哈希表加一个「已凑齐种类数」的计数器——能自然给出这条推广，说明理解的是模型而不是模板。

易错点总结

错误写法：把内层的 while 写成 if：s = "aaabc" → right = 4 时窗口 $[0,4]$ 合格，只结算 left = 0 得 1 就退出，而 left = 1 和 left = 2 同样以 right = 4 为临界值，各自还该贡献 1，正确答案是 3，if 版本只会输出 1。

错误写法：贡献写成 right - left + 1：s = "abc" → 输出 3，而以下标 0 开头的合格子串只有 abc 一个，正确答案是 1。

错误写法：先弹出左端字符再累加贡献 → 结算用的窗口已经不是那个刚刚合格的窗口，当前左端的贡献整段丢失，答案系统性偏小。

错误写法：只在窗口刚好等于「恰好三种字符各一个」时才计数 → 题目要的是「至少包含」，s = "aabc" 里的 aabc 也合格，加上等号限制会大量漏算。

错误写法：外层枚举左端、内层从左端往右扫找临界点，每次都从头开始 → 逻辑正确但退化成 $O(n^2)$，$5 \times 10^4$ 的输入直接超时；双指针的价值就在于左指针不回退。

错误写法：用 HashSet 记录窗口内出现过的字符、弹出左端时直接 remove → 同一字符在窗口里有多份时，弹掉一份就把整个字符从集合里删了，窗口被误判为不合格，答案偏小。必须用计数而非存在性。

错误写法：Go 里把 res 声明成 int32，或在其他语言里用 16 位类型 → 最坏答案接近 $1.25 \times 10^9$，32 位有符号刚好装得下，更窄的类型会溢出成负数。

错误写法：判定条件写成 count[0] + count[1] + count[2] >= 3 → 窗口是 "aaa" 时三者之和也是 3，却一种字符都没凑齐，会把大量非法窗口算进答案。

错误写法：忘记 left 可能追上并超过 right 的情形而额外加 left <= right 的守卫，却把它写进合格判定里 → 本题中窗口合格必然意味着长度至少为 3，left 不会越过 right，多余的守卫反而可能提前中断内层循环、漏掉结算。

相似题目

题目	难度	考察点
76. 最小覆盖子串	困难	同为「至少包含」，但求最短窗口，需在收缩时更新极值
3. 无重复字符的最长子串	中等	条件对延长不封闭而是对收缩封闭，收缩逻辑正好相反
713. 乘积小于 K 的子数组	中等	同样按贡献计数，但贡献取窗口长度，方向是固定右端向左延伸
930. 和相同的二元子数组	中等	「恰好等于」不单调，需用两次「至多」相减来转化
992. K 个不同整数的子数组	困难	同样是恰好型计数，标准解法是维护两个左指针同时滑动
340. 至多包含 K 个不同字符的最长子串	中等	上界型约束，窗口越界时收缩，字符集不定所以要用哈希表计数
424. 替换后的最长重复字符	中等	合格判定依赖窗口内的众数频次，收缩条件不再是简单的计数比较