滑动窗口的一体两面：追安全点 vs 数左端点

有一个笔直的街道上住着 n 个居民，每个居民只会塞给你一种魔法糖果：a 糖、b 糖或 c 糖。你是一个勇者，想要挑战一个成就：“在一次连续的逛街中，收集齐a、b、c 三种糖果”。规则很简单：你从某个起点居民开始，一路往东走，到某个终点居民结束。如果在这段路程中，你的口袋里三种糖至少各有一颗，就算一次成功的逛街。你想知道整条街上一共有多少种成功的逛街方案（不同的起点‑终点组合）。

首先考虑一种情况：如果整条街上根本没有 a 糖，或者没有 b 糖，或者没有 c 糖，那你无论怎么逛，都不可能集齐三种，答案注定是 0。

但假设三种糖都有，游戏正式开始。

你随便选了个起点 left，口袋空空地出发了。每经过一个居民，就收下他给的糖，并且在一个小本子上记下每种糖的数量。你必须在某处结束逛街，但有个诅咒：如果你在逛街结束的时候，口袋里的糖果种类不足三种，诅咒就会发动，把你变成一只青蛙。所以你必须一直往前走，直到集齐三种糖，才敢停下。

你硬着头皮往前走，直到走到某个站点 right 时，惊喜地发现口袋里的糖果种类终于凑齐了三种！你安全了，可以在这里结束逛街了。更重要的是，你发现只要有了 right这个安全点，在 right之后任何一个站点结束都能保证口袋里的三种糖都只多不少，诅咒永远不会发动。所以以 left 为起点的成功方案，就是从 right 到街道末尾的所有站点数，也就是 n - right 种。

你高兴地记下这个数目。但你是个贪婪的冒险者，怎么能满足于一个起点的统计？你要榨干整条街的剩余价值。于是，你把 left 居民给你的那颗糖无情地扔掉——因为接下来你打算从 left+1 出发，left和她的糖果已经是过去时了。扔掉之后，你瞅了一眼小本子：

• 如果本子上三种糖的数量都还大于 0，说明即使从 left+1 出发，走到当前的 right 也已经是安全的，你连一步都不用多走，就可以立刻收割同样的 n - right 种方案。于是你美滋滋地把这个数又加了一遍。
• 如果扔掉 left 的糖后，某种糖的数量变成了 0，口袋里的种类掉回了两种——不好！青蛙诅咒感应到了你的软弱，开始蠢蠢欲动！ 你吓得赶紧从当前的 right 继续向东跑，一边跑一边收新的糖果，直到再次集齐三种，找到一个新安全点 right'。此时你才长舒一口气，把 n - right' 加入账本。

你就这样不断重复：扔掉最左边起点的糖，如果种类不够三就拼命往右跑，直到再次安全；如果够三种就直接算账。直到你的起点 left 越过了街道尽头，这场与青蛙诅咒的博弈才算结束。而你账本上累加的数字，就是所有的成功逛街方案数。

这个不断调整左起点、右安全点的过程，就是滑动窗口。你的左指针 left 就是窗口左边界，右指针 right 是右边界，窗口里的糖果种类始终维持在“刚好集齐三种”的最左安全位置。每当种类够三，你就用 n - right 收割一波答案，然后左指针右移，窗口收缩；一旦种类掉下去，就立刻扩展右指针去救急。两个指针都只往右不回头，全程 O(n)，完美通关。

def numberOfSubstrings(s: str) -> int:
    n = len(s)
    cnt = {'a': 0, 'b': 0, 'c': 0}
    ans = left = 0
    
    for right in range(n):
        # 右指针扩展，收下糖果
        cnt[s[right]] += 1
        
        # 当三种糖果都至少有一颗时，可以安全结束逛街
        while cnt['a'] > 0 and cnt['b'] > 0 and cnt['c'] > 0:
            # 以 left 为起点的所有安全终点数
            ans += n - right
            
            # 扔掉 left 的糖果，左指针右移
            cnt[s[left]] -= 1
            left += 1
            
    return ans

时间复杂度：O(n)，每个指针最多移动 n 次。空间复杂度：O(1)，只维护了一个固定大小的计数字典。

上面的思路直白得像刚拿到驾照的新手上路——左指针每次抬离合都担心熄火。你总觉得还能再优雅一点。

你决定换个角度看这个问题。

刚才是固定左端点，辛辛苦苦找第一个合法的右端点。但如果反过来——固定右端点，去找最远的合法左端点呢？

假设你现在站在位置 right，刚收下这颗糖。此时窗口 [left, right] 内三种糖都齐了。那么对于任意一个比 left 还靠左的起点 left'，子串 s[left':right+1] 里的糖果只会更多，肯定也包含三种。

也就是说，以 right 为终点的合法子串数量，恰好就是 left 的值（左端点可以选 0, 1, 2, …, left-1，一共 left 种可能）。这让你想到了一个更优雅的滑动窗口实现——

你不再需要每找到一个安全点就去算 n - right，而是站在每个右端点上，只问一句话——“最靠右的、让窗口刚好不满足三种糖的左边界在哪？”这个左边界就是 left，而 0 到 left-1 统统合法。

于是你可以在一次遍历中，一边往右走一边默默维护这个 left，每走一步就把 left 加到答案里，连内层 while 里收割答案的环节都省了，循环结构更干净。

def numberOfSubstrings(s: str) -> int:
	n = len(s)
    cnt = {'a': 0, 'b': 0, 'c': 0}
    ans = left = 0
    
    for right in range(n):
        cnt[s[right]] += 1
        
        # 只要三种糖都齐了，就拼命往右推左边界，直到刚好不齐
        while cnt['a'] > 0 and cnt['b'] > 0 and cnt['c'] > 0:
            cnt[s[left]] -= 1
            left += 1
        
        # 此时 left 正好是第一个让窗口不满足三种糖的左端点 => 0 到 left-1 都合法，共 left 个
        ans += left
            
    return ans

时间复杂度:O(n)。空间复杂度:O(1)。

写完你长舒一口气，两个版本都像你的亲儿子一样珍贵。一个追着安全点跑，紧张刺激，像在玩神庙逃亡；一个固定右端点默默计数，像个老会计拨算盘，从容不迫。但无论哪个，青蛙诅咒都只能蹲在街角干瞪眼——你的滑动窗口指针永远不回退，时间复杂度 O(n)，空间 O(1)，一丝破绽都没有。

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。