Count Substrings With K-Frequency Characters I - Video Solutions

Problem Overview: Given a string s and an integer k, count how many substrings contain at least one character that appears k or more times within that substring. The challenge is efficiently checking frequency conditions across all possible substrings.

Approach 1: Brute Force Frequency Counting (O(n^2 * 26) time, O(26) space)

Generate every substring using two nested loops. For each starting index, extend the substring one character at a time while maintaining a frequency array or hash map. After adding each character, check if any character frequency reaches k. If it does, the current substring is valid. This approach is straightforward and demonstrates the core idea, but it becomes slow for large inputs because it evaluates nearly every substring.

This method relies on simple character counting using a hash table or fixed array. It is useful for understanding the problem constraints and verifying correctness before optimizing.

Approach 2: Sliding Window with HashMap (O(n) time, O(26) space)

A more efficient strategy uses a sliding window with two pointers. Expand the right pointer while tracking character frequencies in a hash map. Once any character count becomes k, the current window guarantees that every substring extending further to the right will also satisfy the condition. That means you can immediately add n - right valid substrings to the result.

After counting them, move the left pointer to shrink the window and update frequencies. This ensures the window continues exploring new valid ranges without recomputing counts from scratch. The key insight is that once the frequency threshold is reached, all longer substrings starting at the same left index remain valid.

This approach processes each character a constant number of times, producing linear time complexity. It combines frequency tracking from hash tables with the efficient boundary movement pattern used in many string window problems.

Recommended for interviews: Start by describing the brute force enumeration to show you understand the substring search space. Then move to the sliding window optimization. Interviewers typically expect the O(n) sliding window solution because it demonstrates strong control of two-pointer techniques and frequency tracking.