精通 C++ 中的固定滑动窗口（LeetCode 1876）

Source: Dev.to

Problem

统计长度为 3 的子串中，所有字符均不同的子串数量。

Problem Understanding

给定一个字符串 s。我们需要统计有多少个长度为 3 的子串，其内部的字符全部互不相同。

示例

s = "xyzzaz"

长度为 3 的有效子串：

• "xyz" – 所有字符不同
• "yzz" – z 重复（无效）
• "zza" – z 重复（无效）
• "zaz" – a 重复（无效）

输出

1

Why Sliding Window?

• 子串的大小是固定的（3），因此这是一个 固定滑动窗口 问题。
• 与其生成所有可能的子串（时间复杂度为 O(n · k)），不如维护一个大小为 3 的窗口并一次向右滑动一步。
• 使用频率映射（哈希表）记录当前窗口内字符的计数，从而在 O(1) 时间内检查是否全部不同。

Approach

1. 初始化第一个窗口（前 3 个字符），并在哈希表中记录它们的频率。
2. 检查有效性——如果所有频率都是 1，则答案加一。
3. 向右滑动窗口 一位：
   • 将最左侧字符的计数减一。
   • 将新加入的最右侧字符的计数加一。
   • 重新检查有效性。
4. 重复上述步骤直至遍历完整个字符串。

C++ Implementation

class Solution {
private:
    // Helper to update the answer if the current window is valid
    void counter(unordered_map& umap, int& count){
        bool allDistinct = true;
        for (auto it : umap) {
            if (it.second > 1) {
                allDistinct = false;
                break;
            }
        }
        if (allDistinct) count++;
    }

public:
    int countGoodSubstrings(string s) {
        int count = 0;
        unordered_map umap;

        // First window (first 3 characters)
        for (int i = 0; i (s.size()); ++i) {
            umap[s[i-3]]--;          // remove left character
            umap[s[i]]++;            // add new right character
            counter(umap, count);
        }

        return count;
    }
};

Complexity Analysis

Time Complexity:  O(n)   // each character is processed once
Space Complexity: O(1)   // at most 3 entries in the hashmap

Optimization Tip

由于窗口大小始终为 3，判定字符是否全部不同可以进一步简化：

if (umap.size() == 3)   // all three characters are different
    count++;

如果所有字符都不同，哈希表恰好会包含三个键，这样检查即可在 O(1) 时间完成，无需遍历整个映射。

What I Learned

• 固定大小窗口问题通常比可变大小的更容易实现。
• 频率映射提供了一种高效的方式来强制字符层面的约束。
• 滑动窗口避免了暴力生成子串的开销，将潜在的 O(n · k) 解法转化为 O(n)。