13MS || 100 % || Optimised solution || Java Solution
Intuition\nWe are tasked with finding the number of substrings where at least one character appears k or more times. The key idea is to use a sliding window tec
# Intuition\nWe are tasked with finding the number of substrings where at least one character appears k or more times. The key idea is to use a sliding window technique to explore every substring, and for each substring, we check if a character appears k or more times. If such a substring is found, all suffix substrings starting from that point will also meet the condition.\n\n# Approach\n- `Sliding Window`: The outer loop (with start as the left boundary) explores every starting position for substrings. The inner loop (with end as the right boundary) increments the window size while checking how often each character appears within the current substring.\n- `Counting Frequency`: A frequency array arr of size 26 is used to keep track of the number of occurrences of each character in the current window.\n- `Termination`: As soon as a character appears k or more times in the substring, we count all substrings that can be formed starting from start to the end of the string, since those will also meet the requirement.\n- `Optimization`: Once we find such a substring, we can break the inner loop early, as any longer substrings starting from start will satisfy the condition by including more characters.\n\n# Complexity\n- Time complexity: `O(N^2)`\n\n- Space complexity: `O(1)`\n\n# Code\n```java []\nclass Solution {\n    public int numberOfSubstrings(String s, int k) {\n        int n = s.length();\n        int[] arr = new int[26];\n        int start = 0, end = 0;\n        int ans = 0;\n        while(start < n) {\n            Arrays.fill(arr, 0);\n            end = start;\n            while(end < n) {\n                arr[s.charAt(end)-\'a\']++;\n                if(arr[s.charAt(end)-\'a\'] >= k) {\n                    ans += (n - end);\n                    break;\n                }\n                end++;\n            }\n            if(end == n) break;\n            start++;\n        }\n        return ans;\n    }\n}\n```
['Array', 'String', 'String Matching', 'Java']