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

约 4 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 华为 微软
标签
字符串 哈希表 滑动窗口

题目描述

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

image-20260928224351908

题意分析

字符串只由 a、b、c 组成，统计有多少个连续子串同时包含这三种字符，每种至少出现一次，允许出现多次。

子串由起止位置确定，相同内容出现在不同位置也要分别计数。只检查长度达到三或字符种类出现过都不够，需要保证三种字符在当前同一个区间内齐全。

解法：滑动窗口计数贡献

核心思路

[!blue]

用 count 维护窗口 [left, right] 中三个字符的出现次数。右端每加入一个字符，只要三种频次都大于零，当前窗口就满足条件。

固定这个左端，若当前右端已经齐全，继续把右端向后延伸只会增加字符，不会破坏条件。所以从当前 right 到末尾的所有右端都合法，一次贡献 n - right 个子串。

为什么不会漏掉更早的右端？每次上一轮结束时，未结算的窗口都还不齐全。加入当前字符后才变成合法，说明当前 right 是这个左端第一次可行的终点。收缩后出现的更靠右左端，在此前更小的窗口中也不可能提前齐全。因此从这里开始批量计算，恰好覆盖该左端的全部合法终点。

结算完一个左端后，将它的字符移出并令 left++。如果新窗口仍齐全，继续结算下一左端；否则恢复向右扩张。左端只向前移动，每个起点至多结算一次，而每个合法子串都有唯一的起点，所以计数不会重复。

解题步骤

  1. 初始化三个频次、左端和答案为零。
  2. 右端从左到右移动，把新字符加入计数。
  3. 三种计数都为正时，累加 n - right。
  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)$。左右指针各至多前进 $n$ 次，每个字符至多加入、移出各一次。
  • 空间复杂度：$O(1)$，只保存三个频次和固定数量的变量。

关键点总结

[!green]

  • 按左端批量结算，首次合法右端之后的所有延伸都有效。
  • 每个左端结算后永久移走，因此无需逐一枚举全部子串。
  • 维护频次才能正确处理移出字符后是否仍存在同类字符。

易错点总结

[!yellow]

  • 贡献是可选右端数量 n - right，不是当前窗口长度。
  • 内层使用一次 if 会漏掉同一右端能够同时结算的其他左端，需要持续收缩。
  • 每种字符要求至少一次，不能限制为恰好一次。
  • 只有存在性布尔标记时，移出一个重复字符会误判该字符已经不存在。

相似题目

题目 难度 关联与区别
76. 最小覆盖子串 困难 同样维护覆盖目标字符的窗口；本题统计包含a、b、c的全部子串数量，76返回覆盖目标字符及其重数的最短子串，而不是仅返回长度。
992. K 个不同整数的子数组 困难 本题字符集固定为abc，包含三种即可；原题在任意数组上统计恰好k种值的区间。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/69432121
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！