Count Substrings With K-Frequency Characters II - Video Solutions

Problem Overview: Given a string s and an integer k, count how many substrings contain at least one character whose frequency in that substring reaches k. The brute force approach checks every substring, but the optimal solution uses a sliding window and frequency tracking to count valid substrings efficiently.

Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)

Generate every possible substring using two nested loops. For each starting index, expand the substring one character at a time and maintain a frequency counter. As soon as any character reaches frequency k, the current substring and all longer substrings starting at the same index are valid. Increment the answer accordingly. This approach is simple and demonstrates the core condition, but checking up to O(n^2) substrings makes it too slow for large inputs.

Approach 2: Sliding Window with Frequency Counting (O(n) time, O(1) space)

The optimal method uses a classic sliding window. Maintain two pointers left and right that define the current window and track character frequencies using a small array or hash table. As you expand the window by moving right, update the frequency of the current character. When a character's count reaches k, the window satisfies the condition.

At that point, every substring ending at right and starting anywhere from 0 to left contributes to the result. Shrink the window from the left while the condition still holds to find the minimal valid start. Each step maintains valid frequency counts and ensures each character enters and leaves the window at most once, producing linear time complexity.

This approach works because the constraint depends only on character counts inside the window. Using a frequency array for lowercase letters keeps space constant. The algorithm processes the string once, updating counts and adjusting pointers without revisiting characters.

Recommended for interviews: The sliding window approach is the expected solution. Interviewers want to see whether you recognize that substring counting problems often reduce to maintaining a dynamic window and frequency map. Explaining the brute force first shows understanding of the problem constraints, while implementing the optimized sliding window demonstrates mastery of string processing and two‑pointer techniques.