Count Substrings With K-Frequency Characters I

Count Substrings With K-Frequency Characters I

What is this problem about?

The Count Substrings With K-Frequency Characters I interview question involves a string s and an integer k. You need to count the number of substrings that contain at least one character that appears at least k times.

For example, if $k=2$ and the substring is "abcba", 'a' appears twice and 'b' appears twice. Since at least one character meets the frequency $k$, the substring is counted.

Why is this asked in interviews?

Google uses this problem to evaluate a candidate's ability to handle window constraints and complementary counting. While you can count valid substrings directly, it is often easier to count the total number of substrings and subtract the "invalid" ones (those where all character frequencies are strictly less than $k$). This problem tests your ability to choose the most efficient mathematical path.

Algorithmic pattern used

This problem follows the Sliding Window and Hash Table interview patterns.

1. Use a two-pointer approach to find the number of "invalid" substrings.
2. Expand the right pointer.
3. If any character frequency reaches $k$, the window is no longer "invalid."
4. Shrink the left pointer until all frequencies are back below $k$.
5. For each right, the number of invalid substrings ending there is right - left + 1.
6. Total substrings = $n(n+1)/2$.
7. Result = Total - Invalid.

Example explanation

s = "abacb", k = 2

1. Total substrings for length 5 = 15.
2. Let's find invalid ones (all chars < 2):
   • "a", "b", "ab", "a", "ba", "c", "ac", "bac", "b", "cb" are all valid invalid windows.
3. When we reach "aba" ($right=2$), 'a' frequency is 2. We must shrink from left until 'a' freq < 2.
4. Total "invalid" count = (sum of all valid window lengths).
5. Subtract from 15.

Common mistakes candidates make

• Forgetting the "at least one" rule: Getting confused and trying to find substrings where all characters appear $k$ times.
• Window contraction: Not correctly updating the character counts when moving the left pointer.
• Brute force: Implementing an $O(N^2)$ or $O(N^3)$ solution which will fail on larger strings.

Interview preparation tip

Practice the "At most $K$" pattern. Problems that say "at least one character meets condition" are often simpler to solve as "Total - (all characters fail to meet condition)." This is a common trick in combinatorics and string algorithms.