Python Solution (7 ms) Beats 95%🔥🔥🔥
Time Complexity: O(n)\n\n    class Solution:\n        def numberOfSubstrings(self, s: str, k: int) -> int:\n            n = len(s)\n            char_count = [0]
**Time Complexity:** O(n)\n\n    class Solution:\n        def numberOfSubstrings(self, s: str, k: int) -> int:\n            n = len(s)\n            char_count = [0] * 26\n            left = 0\n            result = 0\n            valid = 0  # Number of characters that have frequency >= k\n\n            for right in range(n):\n                # Update the count for the current character\n                char_count[ord(s[right]) - ord(\'a\')] += 1\n\n                # Check if the current character reaches the count >= k\n                if char_count[ord(s[right]) - ord(\'a\')] == k:\n                    valid += 1\n                \n                # Shrink the window when it\'s no longer valid\n                while valid > 0:  # At least one character has count >= k\n                    # Count all substrings ending at the current \'right\'\n                    result += n - right\n                    \n                    # Move left pointer to reduce window size\n                    char_count[ord(s[left]) - ord(\'a\')] -= 1\n\n                    # If the count of the left character falls below k, reduce valid count\n                    if char_count[ord(s[left]) - ord(\'a\')] == k - 1:\n                        valid -= 1\n                    left += 1\n\n            return result
['Python3']