先说说这题留给我的第一印象：给定一个只包含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[r+1] - prefix_a[L] > 0 prefix_b[r+1] - prefix_b[L] > 0 prefix_c[r+1] - 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]：
| 下标 | 当前字符 | lastA | lastB | lastC | min | ans 变化 |
|---|---|---|---|---|---|---|
| 0 | a | 0 | -1 | -1 | -1，跳过 | ans = 0 |
| 1 | b | 0 | 1 | -1 | -1，跳过 | ans = 0 |
| 2 | c | 0 | 1 | 2 | 0 | ans += 1，ans = 1 |
| 3 | a | 3 | 1 | 2 | 1 | ans += 2，ans = 3 |
| 4 | b | 3 | 4 | 2 | 2 | ans += 3，ans = 6 |
| 5 | c | 3 | 4 | 5 | 3 | ans += 4，ans = 10 |
第 2 行到第 3 行需要仔细看。更新完lastA = 3后，三个最近位置分别是 3、1、2，最小值是 1。这意味着以右端点 3 为结尾的合法子串，左端点只能在 [0, 1] 中选，所以是 2 个，对应s[0..3]和s[1..3]。
这种手动推演非常有帮助。一旦你理解了“为什么所有合法的左端点恰好是一个前缀区间”，后面的公式自然就记住了。
3.3 参考代码（C++ 和 Python）
C++ 版本：
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。说明起点为 0（"bca"）的子串合法，起点为 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 改成 K，last 数组就得换成字典。
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 数组法和滑动窗口模板对你来说就不再是“硬背模板”，而是同一个单调性在两种计数方式下的自然表达。以后再遇到类似的字符串计数题，你就知道该从哪个角度切入，而不是拿到题目先盲目套个双指针上去。
