Sliding Window + HashMap
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n1.Sliding Window Setup:
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.Sliding Window Setup: I maintain two pointers, i and j, where i represents the starting index and j represents the ending index of the current window (substring) under consideration. The goal is to explore all substrings starting from index i and ending at index j or beyond.\n\n2.Character Frequency Map: I use a HashMap to store the frequency of each character within the current window. As I expand the window by moving j to the right, I update the map with the frequency of the character at j.\n\n3.Condition Check: Whenever the character at j has appeared at least k times within the current window, I know that all substrings starting from i and ending at or after j are valid. This is because once a character in the window appears k times, all longer substrings will also have that character appearing k times or more.\n\n4.Counting Substrings: When the condition is met, I calculate the number of valid substrings by adding (n - j) to the count. This captures all possible substrings ending at j or beyond. Then, I shrink the window by moving the i pointer to the right and updating the frequency of the character at i.\n\n5.Repeat Process: I repeat this process, expanding the window by incrementing j and shrinking it as needed, until all valid substrings are counted.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(k)\n# Code\n```java []\nclass Solution {\n    public int numberOfSubstrings(String s, int k) {\n        int i=0;\n        int j=0;\n        int n=s.length();\n        int count=0;\n         HashMap<Character,Integer>mp=new HashMap<>();\n        while(j<n){\n            mp.put(s.charAt(j),mp.getOrDefault(s.charAt(j),0)+1);\n            while(mp.get(s.charAt(j))>=k){\n            count+=(n-j);\n             mp.put(s.charAt(i),mp.get(s.charAt(i))-1);\n             i++;\n            }\n            j++;\n\n        }\n        return count;\n\n    }\n}\n```
['Java']