A bit different interesting approach (not sliding window)
IntuitionThis solution tracks positions where characters reach frequency k, then counts valid substrings by determining all possible starting positions that pai
# Intuition
This solution tracks positions where characters reach frequency k, then counts valid substrings by determining all possible starting positions that pair with each ending position.

<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
1) Track Character Positions: For each character, store its positions in the string
2) Mark Ending Positions: When a character appears k times, mark where its frequency reaches k
3) Count Valid Substrings: For each potential starting position (where a character reaches frequency k), count all valid substrings that can end at any position after it
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

The key insight is avoiding checking each possible substring individually by precomputing valid ending positions and then efficiently counting all valid combinations.

# Code
```javascript []
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var numberOfSubstrings = function(s, k) {
    let res = 0;
    let arr = new Array(s.length).fill(Infinity);
    let count = new Array(26).fill(null).map(() => []);
    for(let i = 0; i < s.length; i++){
        let c = s.charCodeAt(i) - 97;
        count[c].push(i);
        let len = count[c].length;
        if(len >= k) arr[count[c][len - k]] = i;
    }
    for(let i = 0; i < arr.length; i++){
        if(arr[i] == Infinity) continue;
        let end = s.length;
        let j = i - 1;
        res += end - arr[i];
        while(j >= 0 && arr[j] > arr[i]){
            if(arr[j] < end) end = arr[j];
            res += end - arr[i];
            j--;
        }
    }
    return res;

};
```
['Hash Table', 'String', 'JavaScript']