🌟 Beats 100.00% 👏 || Count Sub strings With K-Frequency Characters I
Intuition\n Describe your first thoughts on how to solve this problem. \nThis problem revolves around counting substrings of a string s where a specific charact
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem revolves around counting substrings of a string s where a specific character appears exactly k times. \n\nIterate through the string: For every starting point i in the string, consider every possible substring starting at i and ending at j (i.e., s[i:j]).\n\nTrack character frequency: Use an array freqArr of size 26 (for lowercase English letters) to keep track of how many times each character appears in the substring s[i:j].\n\nCondition to stop: For each character at index j, increment its frequency in freqArr. If at any point, the frequency of the current character matches k, then every substring that starts at i and ends from j to the end of the string will meet the condition.\n\nCounting valid substrings: Once a valid substring is found (i.e., a character appears exactly k times), you can add all substrings starting at i and ending from j to the end of the string to the answer, because adding more characters beyond j will still have that character appear at least k times.\n\nEfficiency consideration: Even though this is a brute-force approach, the inner loop breaks as soon as the condition is met to avoid unnecessary further checks.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet\'s walk through an example where s = "abcabc" and k = 2.\n\nIteration with i = 0:\n\nStart with the substring beginning at index 0.\nInitialize freqArr = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].\nInner Loop with j = 0:\n\nThe character is \'a\'. Increment freqArr[0].\nNow freqArr = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].\n\'a\' has not appeared k=2 times yet, so continue to the next j.\nInner Loop with j = 1:\n\nThe character is \'b\'. Increment freqArr[1].\nNow freqArr = [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].\nNeither \'a\' nor \'b\' has appeared k=2 times yet, so continue to the next j.\nInner Loop with j = 2:\n\nThe character is \'c\'. Increment freqArr[2].\nNow freqArr = [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].\nStill no character appears k=2 times yet. Continue to j = 3.\nInner Loop with j = 3:\n\nThe character is \'a\'. Increment freqArr[0].\nNow freqArr = [2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].\nNow \'a\' appears exactly k=2 times.\nAdd s.length() - j = 6 - 3 = 3 to ans, and break the inner loop.\nThe total count is now ans = 3.\n\nWe continue this process for i = 1, i = 2, and so on, updating freqArr for each new starting point.\n# Complexity\n- Time complexity:O(N^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n![upvote.jpeg](https://assets.leetcode.com/users/images/2ab469ad-d54d-4dc7-b7ca-030b53ff002d_1729412521.519645.jpeg)\n\n# Code\n```javascript []\nvar numberOfSubstrings = function (s, k) {\n    let ans = 0;\n\n    for (let i = 0; i < s.length; i++) {\n        let freqArr = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];\n\n        for (let j = i; j < s.length; j++) {\n            freqArr[s.charCodeAt(j) - 97]++;\n            \n            if (freqArr[s.charCodeAt(j) - 97] == k) {\n                ans += s.length - j\n                break\n            }\n        }\n    }\n\n    return ans;\n};\n```\n```python []\ndef numberOfSubstrings(s, k):\n    ans = 0\n\n    for i in range(len(s)):\n        freqArr = [0] * 26\n\n        for j in range(i, len(s)):\n            freqArr[ord(s[j]) - ord(\'a\')] += 1\n            \n            if freqArr[ord(s[j]) - ord(\'a\')] == k:\n                ans += len(s) - j\n                break\n    \n    return ans\n\n```\n```java []\npublic class Solution {\n    public int numberOfSubstrings(String s, int k) {\n        int ans = 0;\n\n        for (int i = 0; i < s.length(); i++) {\n            int[] freqArr = new int[26];\n\n            for (int j = i; j < s.length(); j++) {\n                freqArr[s.charAt(j) - \'a\']++;\n\n                if (freqArr[s.charAt(j) - \'a\'] == k) {\n                    ans += s.length() - j;\n                    break;\n                }\n            }\n        }\n\n        return ans;\n    }\n}\n\n```\n```c []\n#include <stdio.h>\n#include <string.h>\n\nint numberOfSubstrings(char* s, int k) {\n    int ans = 0;\n    int n = strlen(s);\n\n    for (int i = 0; i < n; i++) {\n        int freqArr[26] = {0};\n\n        for (int j = i; j < n; j++) {\n            freqArr[s[j] - \'a\']++;\n\n            if (freqArr[s[j] - \'a\'] == k) {\n                ans += n - j;\n                break;\n            }\n        }\n    }\n\n    return ans;\n}\n```\n```c++ []\n#include <iostream>\n#include <vector>\n#include <string>\n\nusing namespace std;\n\nint numberOfSubstrings(string s, int k) {\n    int ans = 0;\n\n    for (int i = 0; i < s.length(); i++) {\n        vector<int> freqArr(26, 0);\n\n        for (int j = i; j < s.length(); j++) {\n            freqArr[s[j] - \'a\']++;\n\n            if (freqArr[s[j] - \'a\'] == k) {\n                ans += s.length() - j;\n                break;\n            }\n        }\n    }\n\n    return ans;\n}\n```\n
['Recursion', 'C', 'Simulation', 'Python', 'C++', 'Java', 'TypeScript', 'Python3', 'JavaScript']