Intuitive Sliding Window Solution in C++
---\n\n# Solution Explanation\n\n## Problem\nGiven a string s and an integer k, we need to count the number of substrings where any character appears at least k
---\n\n# Solution Explanation\n\n## Problem\nGiven a string `s` and an integer `k`, we need to count the number of substrings where any character appears at least `k` times. This problem is solved by iterating over possible substrings and using a sliding window approach to efficiently count the substrings that satisfy this condition.\n\n## Approach\nWe use a **sliding window** technique to maintain a window `[start, end]` where:\n- `start` and `end` are pointers defining the current substring.\n- A `count` array of size 26 keeps track of character frequencies within the window.\n\n### Steps:\n1. **Expand the Window**:\n   - For each character at `end`, increment its count in `count`.\n   - Check if any character in the window meets or exceeds the required frequency `k`.\n\n2. **Shrink the Window**:\n   - If any character\u2019s frequency is `\u2265 k`, start shrinking the window from the left by incrementing `start` and decrementing the count of characters as we slide out of the window.\n   - Each time the window meets the criteria, every substring starting from `start` to the end of the string will also meet the criteria. Therefore, add `(n - end)` to the result for all these substrings.\n\n3. **Repeat** until `end` reaches the end of the string.\n\n### Complexity Analysis\n- **Time Complexity**: \\( O(n) \\) \u2014 We traverse the string once with `end`, and within the loop, `start` can also move at most `n` steps.\n- **Space Complexity**: \\( O(1) \\) \u2014 We use a fixed-size `count` array of length 26.\n\n## Code\n\n```cpp\nclass Solution {\npublic:\n    int numberOfSubstrings(string s, int k) {\n        vector<int> count(26, 0);\n        int n = s.length();\n        int start = 0;\n        int result = 0;\n\n        for (int end = 0; end < n; end++) {\n            count[s[end] - \'a\']++;\n            int maxFrequency = *max_element(begin(count), end(count));\n\n            // While there is a character in the current window with a frequency >= k\n            while (maxFrequency >= k && start <= end) {\n                count[s[start] - \'a\']--;  // Slide the window from the left\n                start++;\n                maxFrequency = *max_element(begin(count), end(count));  // Recompute max frequency\n                \n                // Every substring from start to end meets the condition\n                result += (n - end);\n            }\n        }\n        return result;\n    }\n};\n```\n\n## Explanation of Key Lines\n\n- `count[s[end] - \'a\']++`: Tracks the frequency of the character at `end` in the current window.\n- `int maxFrequency = *max_element(begin(count), end(count));`: Checks the maximum character frequency in the current window.\n- `while (maxFrequency >= k && start <= end)`: Shrinks the window from the left if any character frequency reaches `k`.\n- `result += (n - end);`: Adds all valid substrings from `start` to the end of the string to the result.\n\nThis approach efficiently counts all substrings meeting the criteria without needing to explore each substring individually.
['Two Pointers', 'String', 'Sliding Window', 'C++']