★ FEATURED ARTICLE 先说说这题留给我的第一印象给定一个只包含a、b、c三种字符的字符串s统计所有同时包含这三种字符的子串个数。LeetCode 1358 看起来只是众多滑动窗口题里的一道但它其实把“计数”和“窗口”结合的非常典型。第一次做的时候我第一反应还是老套路枚举所有子串再逐个检查里面有没有 a、b、c。结果n一旦到 5e4这个思路直接没戏。这篇文章我会从最直观的暴力做法开始逐步推到两种能 AC 的 O(n) 方案再讲清楚为什么 last 数组法最不容易写错最后聊聊怎么从这道题泛化到更复杂的业务场景。适合正在刷双指针、准备面试或者想系统掌握“固定端点计数”这类题型的读者。1. 题面背后到底在问什么1.1 一句话定义一个“合法子串”题目里的子串是连续的不是子序列。一个子串只要同时出现过a、b、c这三个字符就算合法。重复出现没关系至少一次即可。举个例子输入s abcabc输出10为什么是 10我们把所有合法子串列出来看看abc - 合法 abca - 合法 abcab - 合法 abcabc - 合法 bca - 合法 bcab - 合法 bcabc - 合法 cab - 合法 cabc - 合法 abc - 下标 3..5合法正好 10 个。注意abc出现了两次因为下标不同算两个不同子串。还有一个例子经常用来验证边界s aaacb返回3。原因是以最后一个字符为结尾时合法起点只有下标 0、1、2分别对应aaacb、aacb、acb。1.2 约束条件决定了算法上限题目给出的字符串长度上限是5 * 10^4。如果采用两重循环枚举起点和终点复杂度是 O(n^2)大约要做 25 亿次迭代这在算法题环境里几乎必然超时。更别说很多初学者一开始会写出三重循环先枚举起点再枚举终点最后再遍历中间所有字符检查是否包含三种字符复杂度直接 O(n^3)n 1000都跑不动。所以第一件事不是急着写代码而是认识到这道题需要的至少是 O(n log n)最好是 O(n) 的算法。还有个容易被忽略的细节子串总数最多是n * (n 1) / 2当n 5e4时约为1,250,025,000。这个值在 C 的int范围内勉强放得下但我在工程代码里依然会习惯用long long或 Python 的int省得以后扩展数据范围时出问题。1.3 核心单调性合法起点是连续的很多双指针题能成立靠的是一个单调性质。假设固定右端点r如果起点p对应的子串s[p..r]已经同时包含 a、b、c那么任何比p更靠左的起点比如p - 1对应的子串只会更长字符只会更多所以也必然同时包含 a、b、c。换句话说对同一个右端点而言合法起点是从 0 到某个最大值的一段前缀区间。这个“前缀连续”的性质是所有计数公式的地基。2. 三种能想到的做法以及我最推荐的一种2.1 暴力枚举给没思路时兜底暴力其实也能写只是不 AC。伪代码如下ans 0 for left in range(n): for right in range(left, n): count a/b/c in s[left..right] if count 都 0: ans 1内层每次检查可以用一个长度为 3 的计数器维护复杂度降到 O(n^2)空间 O(1)。但在5e4长度下依然不行。暴力最大的价值是帮你理解问题本身如果求最小长度你会想到双指针如果求个数你会想到“按右端点分组”。先暴力再优化思路会更顺。2.2 前缀和 二分思路直但代码重第二种思路是维护三个字符的前缀出现次数数组。对于每个右端点r我们希望找到一个最小的左端点L使得prefix_a[r1] - prefix_a[L] 0 prefix_b[r1] - prefix_b[L] 0 prefix_c[r1] - prefix_c[L] 0因为随着左端点L变大窗口缩短包含三字符的可能性单调下降所以可以二分查找。复杂度 O(n log n)也算合格。但我不推荐把这题写成二分原因有两个代码明显更长还要分别维护三个前缀数组。这题的字符集合固定且极小有更简洁的线性做法。二分思路适合作为一种思维训练真正写题时没必要。2.3 最近出现位置last 表只关心最后一次最后是这题最优雅的解法。核心思想是对每个右端点i如果能统计出a、b、c最近一次出现的位置那么以i为右端点的所有合法子串数量就很好算。把三种字符最后一次出现的位置记为last_a、last_b、last_c。只有当三个值都不等于 -1 时才说明当前字符串已经把三种字符都见过了。合法左端点必须小于等于这三个位置中的最小值否则会漏掉其中某个字符。所以最小值是min(last_a, last_b, last_c)。左端点可以从 0 取到这个最小值一共min 1个。于是每一轮累加answer min(last_a, last_b, last_c) 12.4 三种方案对比方法时间复杂度空间复杂度代码量推荐度暴力枚举O(n^2) 或 O(n^3)O(1)很少只用于理解题意前缀和 二分O(n log n)O(n)中等不推荐last 数组O(n)O(1)很少最推荐双指针滑动窗口O(n)O(1)中等推荐但要清楚模板实际写下来last 数组法最直观也不容易踩到双指针模板的坑。3. 手把手走一遍 last 数组法3.1 为什么 last 数组天然不重不漏很多读者担心按右端点累加会不会重复计数。答案是不会。每个合法子串都有且仅有一个右端点。当我们以右端点分组时每个子串只会被它自己的右端点处理到不同组之间没有交集。而同一组内用min(last) 1正好枚举了所有可能的左端点。这样既不会漏也不会重。3.2 用abcabc完整模拟以s abcabc为例初始last [-1, -1, -1]下标当前字符lastAlastBlastCminans 变化0a0-1-1-1跳过ans 01b01-1-1跳过ans 02c0120ans 1ans 13a3121ans 2ans 34b3422ans 3ans 65c3453ans 4ans 10第 2 行到第 3 行需要仔细看。更新完lastA 3后三个最近位置分别是 3、1、2最小值是 1。这意味着以右端点 3 为结尾的合法子串左端点只能在 [0, 1] 中选所以是 2 个对应s[0..3]和s[1..3]。这种手动推演非常有帮助。一旦你理解了“为什么所有合法的左端点恰好是一个前缀区间”后面的公式自然就记住了。3.3 参考代码C 和 PythonC 版本class Solution { public: int numberOfSubstrings(string s) { int last[3] {-1, -1, -1}; int n s.size(); int ans 0; for (int i 0; i n; i) { last[s[i] - a] i; if (last[0] ! -1 last[1] ! -1 last[2] ! -1) { int mn min({last[0], last[1], last[2]}); ans mn 1; } } return ans; } };Python 版本class Solution: def numberOfSubstrings(self, s: str) - int: last [-1] * 3 ans 0 for i, ch in enumerate(s): last[ord(ch) - ord(a)] i if all(x ! -1 for x in last): ans min(last) 1 return ans代码里一个值得留意的点是字符映射。题目保证只有a/b/c所以s[i] - a的结果只可能是 0、1、2。如果输入里混进其他字符这个写法会越界但题目约束已经排除了这种情况。4. 双指针滑动窗口另一种常见模板与容易踩的坑4.1 固定左端点累加n - right双指针做法通常更被竞赛玩家熟悉但写错概率也更高。第一个模板是“固定左端点向右扩展右端点直到窗口合法”。核心逻辑用left和right维护当前窗口。right不断向右扩展加入新字符。当窗口已经包含三种字符时此时right就是“以 left 为起点”的第一个合法右边界。那么以left为起点的合法子串可以延伸到字符串末尾任意位置数量是n - right。累加后把left右移一位继续判断新的起点。C 模板class Solution { public: int numberOfSubstrings(string s) { int n s.size(); int cnt[3] {0, 0, 0}; int kinds 0; int left 0; int ans 0; for (int right 0; right n; right) { int idx s[right] - a; cnt[idx]; if (cnt[idx] 1) kinds; while (kinds 3) { ans n - right; int leftIdx s[left] - a; cnt[leftIdx]--; if (cnt[leftIdx] 0) kinds--; left; } } return ans; } };关键点是ans n - right发生在while内部而不是外面。每次窗口合法时right都是当前left对应的最小合法右边界。如果在while外面只加一次会漏掉后面所有更长的合法子串。4.2 固定右端点累加left另一个模板是固定右端点不断收缩左端点直到窗口不合法。此时left的含义是“第一个不合法起点”而0到left - 1都是合法起点所以每轮累加left。Python 模板class Solution: def numberOfSubstrings(self, s: str) - int: n len(s) cnt [0] * 3 left 0 ans 0 for right in range(n): cnt[ord(s[right]) - ord(a)] 1 while cnt[0] 0 and cnt[1] 0 and cnt[2] 0: cnt[ord(s[left]) - ord(a)] - 1 left 1 ans left return ans这个模板看第一次会觉得怪ans加的是left而且while里已经把窗口弄得不合法了为什么还能算合法数量因为循环结束后的left其实就是“以当前 right 为结尾的合法子串数量”。举个例子遍历到某个right窗口变成bca然后不断左移移到ca时不再合法这时left 1。说明起点为 0bca的子串合法起点为 1 的ca不合法合法数量恰好等于left。两个模板都能 AC但我个人认为 first 模板和 last 数组更匹配因为“最小合法右边界”更好理解。选择哪一种都可以关键是不要在一道题里混用。4.3 我踩过的三个坑先说第一个坑ans加的位置不对。很多人会把ans n - right写到while外导致只计算了每个窗口的位置而不是所有以left为起点的子串数量。这个错误在样例短的时候不明显一旦字符串变长答案会瞬间少一大截。第二个坑是盲目回退right。有些同学把双指针理解成“找到一个合法窗口就去枚举所有左端点”然后让right回到left 1重新开始复杂度退化回 O(n^2)。双指针之所以高效是因为right只需要向右移动不需要回头。第三个坑是计数变量维护不完整。比如在left移动后没有同步更新cnt导致窗口“假合法”或“假不合法”。维护kinds这个变量时要记得只有在cnt从 0 变成 1 时才加一在cnt从 1 变成 0 时才减一。4.4 两种写法的时间与空间细节双指针的时间复杂度是 O(n)因为每个字符最多被right访问一次、被left移除一次。空间复杂度是 O(1)只用了固定大小的数组。last 数组法同样 O(n) 时间和 O(1) 空间。两者的差别主要是代码风格和思维模型last 数组法更接近“对每个右端点统计答案”天然不会重复双指针更接近“对每个左端点找最小右端点”需要理解窗口收缩的时机。提示如果面试官让你证明正确性last 数组法更容易讲清楚“每个子串有唯一右端点所以按右端点分组、再累加每个分组内的合法起点数量不重不漏。”这句话本身就是一份很漂亮的证明。5. 从固定三字符到 K 个目标字符5.1 用字典实现 K 字符通解真实业务里不太可能永远只有 a、b、c 三种目标。如果把目标集合从 3 改成 Klast 数组就得换成字典。Python 通解版本class Solution: def numberOfSubstrings(self, s: str, targets: set[str]) - int: last {} ans 0 for i, ch in enumerate(s): if ch in targets: last[ch] i if len(last) len(targets): earliest min(last.values()) ans earliest 1 return ans这里用len(last)判断是不是所有目标字符都已经出现过。因为last字典的 key 只会来自目标集合当它的大小等于目标数量时就说明全部见过了。复杂度是 O(n * K)因为每轮可能要对 K 个值取 min。当 K 很小比如 3、4、10这完全没有问题。如果 K 很大就需要用堆或线段树求最小last值但工程上很少会遇到目标字符上百的情况。5.2 和“最小覆盖子串”的关系如果你刷过经典的“最小覆盖子串”问题会发现这题和它是同一条路子用窗口统计目标字符出现次数然后用某种“合法条件”驱动左右指针移动。区别在于最小覆盖子串要求找到最短的那个窗口本题要求统计所有合法窗口的数量。换句话说一个是最值问题一个是计数问题。双指针模板在处理最值和计数时写法会有微妙差异。计数题往往要利用“合法窗口的右端点可以继续延伸到末尾”这个性质一次性累加多个子串。5.3 面试官会怎么追问面试官围绕这题可以问很多扩展如果字符串只包含 a/b/c但有 10^5 长度答案会溢出吗如果目标字符是 K 个还能不能用滑动窗口如果要求每个目标字符至少出现两次怎么做如果要求统计不重复的合法子串按内容去重还能用窗口吗前两个问题我们上面已经回答了大半。第三个问题可以把 last 数组扩展为“倒数第二次出现位置”或者用双指针维护窗口内每个字符的计数再加一个“是否全部满足出现次数要求”的判断。第四个问题会麻烦很多一般需要后缀自动机之类的数据结构面试中不常考。6. 这道题在业务代码里还能怎么用6.1 日志聚合一个时间窗口内的事件类型是否齐全假设一个系统在持续产生日志每条日志带着事件类型我们需要统计“过去一段时间内A、B、C 三类事件都出现过”的次数。这不就是 1358 的原始模型吗字符串变成日志流字符变成事件类型子串变成滑动的日志窗口。用 last 数组法可以实时维护每个事件类型最近一次出现的位置然后快速知道“当前时间点往前推多少条日志开始是所有类型都已具备的时间范围”。类似地告警系统中要检测“磁盘、内存、网络在同一个检查周期内同时异常”也可以沿用这个思路。6.2 基因序列与文本片段统计处理基因序列时DNA 字符串通常只有A、C、G、T四种碱基。如果想知道“包含 A、C、G 三种碱基的片段有多少个”last 数组法直接适用只需要把字符映射改成碱基映射。文本分析里也有类似问题给定一篇文章的字符序列统计包含数字、字母、符号三类字符的连续片段数量。这本质上就是 K 字符版本的通解问题。6.3 工程选型直觉先看字符集大小再选算法从工程角度我不会一上来就套滑动窗口模板而是先问自己三个问题目标字符集合固定吗多大需要实时更新还是离线统计数据规模大概多大如果目标集合很小且固定last 数组法最合适如果目标集合动态变化字典版本更灵活如果数据量巨大且需要并行可以考虑分段统计再合并双指针边界信息。这种“先分场景再定方案”的思维比背诵模板重要得多。根据我个人刷题和面试的经验1358 这道题最好的学习方式不是直接看题解而是先自己从暴力开始推为什么 O(n^2) 不行为什么右端点固定后合法起点是连续的为什么按右端点分组不会重复。推完这三步last 数组法和滑动窗口模板对你来说就不再是“硬背模板”而是同一个单调性在两种计数方式下的自然表达。以后再遇到类似的字符串计数题你就知道该从哪个角度切入而不是拿到题目先盲目套个双指针上去。
阅读完成 · 觉得有帮助？
