Given a string s and an integer k, return the total number of substrings of s where at least one character appears at least k times.

Note: A substring is a contiguous sequence of characters within a string. For example, "edu" is a substring of "educative". 

Constraints:

• $1 \leq$ s.length $\leq 3 \times 10^{3}$

• $1 \leq$ k $\leq$ s.length

• s consists only of lowercase English letters.

A brute-force approach to this problem would involve checking all possible substrings and counting character frequencies to see if any character appears exactly k times. However, this becomes inefficient for longer strings due to the large number of substrings and repeated computations.

To avoid this, a sliding window technique can be used. The idea is to move through the string with two pointers that define a window, while maintaining a frequency count of characters within it. The right pointer extends the window forward one character at a time, while the left pointer adjusts the starting point of the window when necessary. As the window expands, a frequency table keeps track of how many times each character appears inside the current window. Alongside this, a separate counter tracks how many characters have reached a frequency of exactly k.

When a character in the current sliding window reaches a frequency of exactly k, the window contains at least one valid character (one that appears exactly k times). This makes the current window s[left...right] valid. Here’s the key insight: all substrings that start at the current left position and end at any position from right to the end of the string will still include this valid window, and therefore, will also be valid substrings. That’s because the portion of the string from left to right already satisfies the condition, and appending more characters to the end won’t remove that property (until the window is explicitly shrunk from the left, which is handled later). So, the number of such valid substrings is simply:

$all~valid~subarrays$ = $length~of~s ~- ~right~index$

Once a valid window is found, the algorithm begins shrinking it from the left to avoid overcounting or including invalid substrings. As the left pointer moves forward, the character it leaves behind is removed from the frequency table. If that character’s frequency was exactly k before removal, the counter of k-frequency characters is updated accordingly. Shrinking continues only as long as at least one character still has frequency exactly k. Once that condition no longer holds, the window stops shrinking and the right pointer resumes expanding the window.

By repeatedly expanding from the right and shrinking from the left, while keeping frequency counts up to date, the algorithm efficiently accounts for all valid substrings.

Let’s look at the algorithm steps:

1. Initialize the following variables:

   1. n: This is the length of the input string s.

   2. freq: This is a list of size 26 to count the frequency of each lowercase letter in the current window. Using a fixed-size array for frequency counting is better than a dictionary when dealing with a known set of characters, like lowercase English letters, because arrays are faster to access and use less memory. As there are only 26 possible letters, an array gives a simple and efficient way to track their frequencies.

   3. chars_with_k: This is the number of characters in the current window that appear exactly k times.

   4. total: This is the final count of valid substrings.

   5. left: This is the left boundary of the sliding window (initially at index 0).

2. Start expanding the sliding window. Iterate over the string, s, using the right pointer and each character, char.

   1. Increment the frequency of the char.

   2. If the frequency of char equals k, increment chars_with_k.

   3. While at least one character in the window appears exactly k times (chars_with_k > 0), the algorithm does the following:

      1. All substrings from left to right are valid, so add n - right to total.

      2. Shrink the window from the left, i.e., remove the leftmost element from the window:

         1. If the leftmost character’s frequency equals k, reduce chars_with_k by 1.

         2. Reduce the frequency of the character at s[left] and move the left pointer one step to the right.

3. After processing the entire string, return the total as the number of valid substrings.

The slides below help to understand the solution in a better way.