O(n) solution using sliding window and hash map. Intuition and approach explained. Beginner friendly
Intuition\n Describe your first thoughts on how to solve this problem. \nMy first thought on seeing "counting substrings satisfying some condition..." was to us
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMy first thought on seeing "counting substrings satisfying some condition..." was to use sliding window technique.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSince it involved frequency of characters, we would need a hashmap (or a simple array of size 26).\n- Have two variables i.e left and right to indicate the current window.\n- Initially both left and right are initialized to 0 (window size = 0).\n- Grow the window by incrementing the right pointer, at the same time, update the character frequency.\n- After updating the character frequency, check if the freq is >= k.\n- If yes then add all the substrings possible from s[left]....s[right]....s[n-1]. NOTE: The substrings are of the form : s[left]..s[right], s[left]...s[right]s[right+1], .... , s[left]...s[n-1].\n- On close observation, the number of such substrings is same as n - right i.e   res += n - right . (n = s.length()).\n- Also keep shrinking the window by incrementing the left pointer till the condition fails.\n- Dont forget to update the character frequency while shrinking the window.\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\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    {\n        \n        map<char, int> char_freq;\n        int left, right, n, res;\n        left = right = res = 0 ;\n        n = s.length();\n\n        for(right = 0 ; right < n ; right++)\n        {\n            char curr_char = s[right];\n            char_freq[curr_char]++;\n\n            while(char_freq[curr_char] >= k)\n            {\n                res += n - right; //Number of substrings starting from left index.\n                char_freq[s[left]]--;\n                left++;\n            }\n\n        }\n\n        return res;\n        \n    }\n};\n```
['Hash Table', 'String', 'Sliding Window', 'C++']