[Java/C++/Python] Sliding Window, O(n)
Intuition\n(n + 1) * n // 2 substrings in total.\nFind the number of substrings,\neach char appears at most  k - 1 times.\n\n\n# Intuition2\nNo problem II in th
# **Intuition**\n`(n + 1) * n // 2` substrings in total.\nFind the number of substrings,\neach char appears at most  `k - 1` times.\n<br>\n\n# **Intuition2**\nNo problem **II** in the contest?\nUpvote this solution,\nand submit it directly in next contest!\n<br>\n\n# **Explanation**\nSolve with sliding window:\n\nEach iteration,\nappend `s[j]` on the right,\nwhile `count[s[j]] >= k`,\nmove the left pointer until it\'s not.\ncount the substring ending with `s[j]` in the window.\nremove them from result.\n<br>\n\n# **Complexity**\nTime `O(n)`\nSpace `O(1)`\n<br>\n\n```Java [Java]\n    public int numberOfSubstrings(String s, int k) {\n        int n = s.length(), res = (n + 1) * n / 2;\n        int[] count = new int[26];\n        for (int i = 0, j = 0; j < n; j++) {\n            char c = s.charAt(j);\n            count[c - \'a\']++;\n            while (count[c - \'a\'] >= k) {\n                char leftChar = s.charAt(i);\n                count[leftChar - \'a\']--;\n                i++;\n            }\n            res -= j - i + 1;\n        }\n        return res;\n    }\n```\n\n```C++ [C++]\n    int numberOfSubstrings(string s, int k) {\n        int n = s.length(), res = (n + 1) * n / 2;\n        unordered_map<char, int> count;\n        for (int i = 0, j = 0; j < n; j++) {\n            count[s[j]]++;\n            while (count[s[j]] >= k)\n                --count[s[i++]];\n            res -= j - i + 1;\n        }\n        return res;\n    }\n```\n\n```py [Python3]\n    def numberOfSubstrings(self, s: str, k: int) -> int:\n        n = len(s)\n        res = (n + 1) * n // 2\n        count = Counter()\n        i = 0\n        for j in range(n):\n            count[s[j]] += 1\n            while count[s[j]] >= k:\n                count[s[i]] -= 1\n                i += 1\n            res -= j - i + 1\n        return res\n```\n
['C', 'Python', 'Java']