Count Substrings with K-Frequency
Intuition\n Describe your first thoughts on how to solve this problem. \nFirstly I thought of using the sliding window approach as there is k.\n# Approach\n Des
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirstly I thought of using the sliding window approach as there is k.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSliding Window:\n\nWe use two pointers, i and j, to represent the sliding window. i is the start of the window, and j is the end of the window.\n\nAs we expand the window by moving j, we keep track of the frequency of characters within the window using a hash map (freq).\n\nFrequency Map:\n\nThe hash map (freq) stores the frequency of each character in the current window.\n\nExpand and Contract the Window:\n\nFor each character s[j], we increment its frequency in the hash map.\n\nIf the frequency of s[j] is greater than or equal to k, it means we have found a valid substring.\n\nWe then contract the window by moving i and decrementing the frequency of s[i] until the frequency of s[j] is less than k.\n\nCount Valid Substrings:\n\nFor each valid window, we add n - j to the count because all substrings starting from i to j and ending at any position from j to n-1 are valid.\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int numberOfSubstrings(string s, int k) {\n        int n = s.size();\n        int count = 0;\n        unordered_map<char, int> freq;\n        \n        for(int i=0, j=0; j<n; j++ ){\n            freq[s[j]]++;\n            while(freq[s[j]] >= k){\n                count += n-j;\n                freq[s[i]]--;\n                i++;\n            }\n        }\n        return count;\n    }\n};\n```
['C++']