Simple Brute Force
Intuition\n#### The key idea is to explore all possible substrings of s and, for each substring, check if any character appears k or more times. This can be don
# Intuition\n#### The key idea is to explore all possible substrings of s and, for each substring, check if any character appears k or more times. This can be done by generating all substrings and counting the frequency of each character for each substring. If at least one character satisfies the condition of appearing k or more times, we increase the count.\n\n#### However, this approach is not optimal since generating all substrings leads to a time complexity of O(n^2), and then checking each substring to see if it has a character appearing k times adds further complexity. Still, this brute-force solution gives a correct answer.\n\n# Approach\n#### 1. **Generate All Possible Substrings :**\n- A substring is defined as any contiguous part of the string s. To generate all substrings, we need to iterate over all possible starting points (i) and all possible ending points (j) for each starting point.\n- This can be done using two loops:\n -- The outer loop fixes the starting point i (runs from 0 to n-1).\n -- The inner loop fixes the ending point j (runs from i to n-1).\n\n#### 2. **Use a Frequency Map to Track Character Counts :**\n- For each substring starting at i and ending at j, we need to check how many times each character appears in that substring.\n- We use an unordered_map<char, int> (hash map) to store the frequency of each character in the current substring.\n- For every new character added to the substring (as j increases), we update the frequency in the map.\n#### 3. **Check if Any Character Appears k Times :**\n- After updating the frequency map for the substring ending at j, we need to check whether any character in the current substring has appeared at least k times.\n- This is done by iterating over the map and checking if any character\'s frequency is greater than or equal to k. If this condition is satisfied, we set a flag (f = true) and break out of the loop.\n#### 4. **Count Valid Substrings :**\n- If the flag f is set to true (i.e., at least one character in the current substring appears k times), we increment the count c for valid substrings.\n\n#### 5. **Return the Total Count :**\n- Once both loops finish, the final count c represents the total number of substrings where at least one character appears at least k times. This count is returned as the result.\n\n# Example Walkthrough\n### Let\u2019s take an example with s = "abbc" and k = 2:\n\n1. **Outer Loop (i = 0) :**\n- Starting point i = 0, substrings generated: "a", "ab", "abb", "abbc"\n- Map updates:\n-- For "a": {a: 1} \u2192 No character appears k = 2 times.\n-- For "ab": {a: 1, b: 1} \u2192 No character appears k = 2 times.\n-- For "abb": {a: 1, b: 2} \u2192 b appears 2 times, so this substring is valid.\n-- For "abbc": {a: 1, b: 2, c: 1} \u2192 b appears 2 times, so this substring is valid.\n-- Valid substrings so far: "abb", "abbc"\n\n2. **Outer Loop (i = 1) :**\n- Starting point i = 1, substrings generated: "b", "bb", "bbc"\n- Map updates:\n-- For "b": {b: 1} \u2192 No character appears k = 2 times.\n-- For "bb": {b: 2} \u2192 b appears 2 times, so this substring is valid.\n--  For "bbc": {b: 2, c: 1} \u2192 b appears 2 times, so this substring is valid.\n-- Valid substrings so far: "bb", "bbc"\n\n3. **Outer Loop (i = 2) :**\n\n- Starting point i = 2, substrings generated: "b", "bc"\n- Map updates:\n-- For "b": {b: 1} \u2192 No character appears k = 2 times.\n-- For "bc": {b: 1, c: 1} \u2192 No character appears k = 2 times.\n- No valid substrings found for i = 2.\n\n4. **Outer Loop (i = 3) :**\n\n- Starting point i = 3, substrings generated: "c"\n- Map updates:\n-- For "c": {c: 1} \u2192 No character appears k = 2 times.\n-- No valid substrings found for i = 3.\n\n5. **Final Count :**\n- The valid substrings found are: "abb", "abbc", "bb", and "bbc". Hence, the total count c is 4.\n\n# Code\n```cpp []\nint numberOfSubstrings(string s, int k) {\n    int c=0;\n\n    for(int i=0;i<s.size();i++){\n        unordered_map<char, int> m;\n        for(int j=i;j<s.size();j++){\n            m[s[j]]++; \n                \n            bool f=false;\n            for (auto x : m){\n                if(x.second>=k){\n                    f=true;\n                    break;\n                }\n            }\n                \n            if(f) c++;\n        }\n    }\n\n    return c;\n}\n```\n\n``` Java []\npublic int numberOfSubstrings(String s, int k) {\n    int c = 0;\n        \n    for (int i = 0; i < s.length(); i++) {\n        HashMap<Character, Integer> charCount = new HashMap<>();\n            \n        for (int j = i; j < s.length(); j++) {\n            charCount.put(s.charAt(j), charCount.getOrDefault(s.charAt(j), 0) + 1);\n                \n            boolean valid = false;\n            for (int freq : charCount.values()) {\n                if (freq >= k) {\n                    valid = true;\n                    break;\n                }\n            }\n                \n            if (valid) {\n                c++;\n            }\n        }\n    }\n        \n     return c;\n}\n```\n\n``` Python []\ndef numberOfSubstrings(s: str, k: int) -> int:\n    c = 0\n    for i in range(len(s)):\n        char_count = {}\n        for j in range(i, len(s)):\n            char_count[s[j]] = char_count.get(s[j], 0) + 1\n            valid = False\n            for freq in char_count.values():\n                if freq >= k:\n                    valid = True\n                    break\n            if valid:\n                c += 1\n    return c\n```\n\n
['Python', 'C++', 'Java']