Mastering Fixed Sliding Window in C++ (LeetCode 1876)

Today I solved a beautiful Sliding Window problem that perfectly demonstrates how fixed-size windows work.

Problem:

Count substrings of size 3 with all distinct characters.

Problem Understanding

We are given a string s. We need to count how many substrings of length 3 contain all distinct characters.

Example

Input:

s = "xyzzaz"

Valid substrings of length 3:

"xyz"

"yzz" (z repeated)

"zza"

"zaz"

Output:

1

Why Sliding Window?

1. Since the substring size is fixed (3), this is a Fixed Sliding Window problem.
2. Instead of generating all substrings (which would be inefficient), we:
3. Maintain a window of size 3.
4. Use a frequency map to track character counts.
5. Slide the window one step at a time.
6. Check if all characters are distinct.

Approach

Step 1 -> Initialize first window (size 3)

Add first 3 characters into a hashmap.

Step 2 -> Check validity

If all frequencies are 1 → count it.

Step 3 -> Slide the window

For every next position

• Remove left character
• Add new right character
• Check validity again
• Repeat until the end.

C++ Implementation

class Solution {
private:
    void counter(unordered_map<char,int>& umap, int& count){
        bool res = true;
        for(auto it : umap){
            if(it.second > 1){
                res = false;
                break;
            }
        }
        if(res) count++;
    }

public:
    int countGoodSubstrings(string s) {
        int count = 0;
        unordered_map<char,int> umap;

        // First window
        for(int i = 0; i < 3; i++)
            umap[s[i]]++;

        counter(umap, count);

        // Slide window
        for(int i = 3; i < s.size(); i++){
            umap[s[i-3]]--;
            umap[s[i]]++;

            counter(umap, count);
        }

        return count;
    }
};

Complexity Analysis

Time Complexity: O(n) -> Each character is processed once.
Space Complexity: O(1)

Window size is fixed (at most 3 characters in map).

Optimization Tip

Since window size is always 3, we can simplify the check . Instead of iterating over the entire map, we can just check:

if(umap.size() == 3)
    count++;

Because if all characters are distinct, the map size will be 3.Cleaner and faster.

What I Learned

-> Fixed window problems are simpler than variable window problems.

-> Frequency maps help validate constraints efficiently.

-> Sliding window avoids brute-force substring generation.

-> Small problem. Big pattern clarity.