Easiest HashMap solution! Detailed Explanation provided.
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to store the frequency of each character in subtsring. So we need a map to coun
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to store the frequency of each character in subtsring. So we need a map to count. Now We go for the Brute force approach to form all substrings starting at each index. However we don\'t need to actually form them. We just need to store characters count in the map. If after addition of character, it\'s frequency is >= k, then going forward every addition to that substring is also valid. So we just store the index and break out. We add the no. of valid substrings it can form and return the count.\n\n\n# Complexity\n- Time complexity: O(N*N) * Time for Map(Avg. case O(1) for Unordered)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(M) Maximum all characters needed to be stored in map.\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 cnt=0;\n        unordered_map<char, int> mpp;\n        for(int i=0; i<s.length(); i++) {\n            int found = -1;\n            for(int j=i; j<s.length(); j++) {\n                mpp[s[j]]++;\n                if(mpp[s[j]] >= k) {\n                    found = j;\n                    break;\n                }\n            }\n            cout<<found<<endl;\n            if(found != -1) cnt += s.length() - found;\n            mpp.clear();\n        }\n        return cnt;\n    }\n};\n```
['Hash Table', 'String', 'C++']