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

Source: Dev.to

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

s = "xyzzaz"

Valid substrings of length 3:

• "xyz" – all distinct
• "yzz" – z repeated (invalid)
• "zza" – z repeated (invalid)
• "zaz" – a repeated (invalid)

Output

1

Why Sliding Window?

• The substring size is fixed (3), so this is a fixed sliding window problem.
• Instead of generating all possible substrings (which would be O(n · k)), we maintain a window of size 3 and slide it one step at a time.
• A frequency map (hash map) tracks character counts inside the current window, allowing us to check distinctness in O(1) per slide.

Approach

1. Initialize the first window (first 3 characters) and fill a hashmap with their frequencies.
2. Check validity – if all frequencies are 1, increment the answer.
3. Slide the window one position to the right:
   • Decrease the count of the leftmost character.
   • Increase the count of the new rightmost character.
   • Re‑check validity.
4. Repeat until the end of the string.

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

Since the window size is always 3, the distinctness check can be simplified:

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

If all characters are distinct, the hashmap will contain exactly three keys, making the check O(1) without iterating over the map.

What I Learned

• Fixed‑size window problems are often simpler than variable‑size ones.
• Frequency maps provide an efficient way to enforce character‑level constraints.
• Sliding windows avoid the overhead of brute‑force substring generation, turning a potentially O(n · k) solution into O(n).