Count Substrings in one pass.
IntuitionApproachOur aim is to count the number of substrings where no character appears at least (k) times. It starts by calculating the total number of substr
# Intuition

# Approach
Our aim is to count the number of substrings where no character appears at least \(k\) times. It starts by calculating the total number of substrings in the string using the formula `(n * (n + 1)) / 2`, where \(n\) is the string length. Then, it uses a sliding window technique with two pointers, \(i\) and \(j\), to go through the string. As we move the right pointer \(j\), we track the frequency of characters in the window. If any character reaches \(k\) occurrences, we move the left pointer \(i\) to shrink the window until the condition is violated. For each valid window, we subtract the number of substrings ending at \(j\) but starting within the window from the total. This ensures that only substrings where no character appears \(k\) or more times are counted.

# Complexity
- Time complexity:
O(n)

- Space complexity:
O(1)

# Code
```cpp []
class Solution {
public:
    int numberOfSubstrings(string s, int k) {
        int n = s.size();
        int totalSubs = (n * (n + 1)) / 2;
        unordered_map<char, int> mpp;
        int i = 0, j = 0;
        while (j < n) {
            mpp[s[j]]++;
            while (mpp[s[j]] >= k) {
                mpp[s[i]]--;
                i++;
            }
            totalSubs -= j - i + 1;
            j++;
        }
        return totalSubs;
    }
};
```
['C++']