#3325

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Count Substrings With K-Frequency Characters I

Calculate the total number of substrings where at least one character repeats k times using a sliding window efficiently.

hash table string sliding window

Problem Statement

Given a string s consisting of lowercase letters and an integer k, compute the total number of contiguous substrings where at least one character appears at least k times. The challenge lies in efficiently tracking character frequencies to avoid checking all possible substrings individually.

For example, if s = "abacb" and k = 2, the valid substrings are counted based on repeated character occurrences. Similarly, for s = "abcde" with k = 1, all substrings are valid since each character appears at least once. Constraints are 1 <= s.length <= 3000 and 1 <= k <= s.length.

Examples

Example 1

Input: s = "abacb", k = 2

Output: 4

The valid substrings are:

Example 2

Input: s = "abcde", k = 1

Output: 15

All substrings are valid because every character appears at least once.

Constraints

1 <= s.length <= 3000
1 <= k <= s.length
s consists only of lowercase English letters.

Solution Approach

Sliding Window with Frequency Map

Maintain a sliding window from left to right and use a hash table to track character counts. Expand the window until a character count reaches k, then record valid substrings ending at the current right index.

Fix Left Index and Expand Right

Iterate over each possible starting index as the left boundary. Expand the right boundary, updating character frequencies in the hash map, and count the number of valid substrings efficiently without re-scanning.

Optimizations to Reduce Redundant Checks

Stop expanding the window once all character counts are insufficient to reach k, as further expansion cannot yield new valid substrings. This avoids unnecessary computations for longer windows.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) in the worst case due to nested left-right iterations but often performs better with early stopping. Space complexity is O(1) or O(26) for the fixed alphabet hash map.

What Interviewers Usually Probe

Ask about edge cases where k is larger than substring length.
Check if the candidate correctly maintains character counts in the sliding window.
Expect recognition of early stopping to avoid unnecessary substring checks.

Common Pitfalls or Variants

Common pitfalls

Not updating the frequency map correctly when moving the left index.
Counting substrings multiple times by not fixing the left index properly.
Assuming all characters must appear k times instead of at least one.

Follow-up variants

Count substrings where exactly one character appears k times.
Find the longest substring where at least one character frequency is at least k.
Apply the same method to strings with uppercase letters or digits, adjusting the hash map.

FAQ

What is the main approach for Count Substrings With K-Frequency Characters I?

Use a sliding window with a hash table to track character frequencies, expanding the right boundary and fixing the left to count valid substrings efficiently.

Can this problem be solved without a hash map?

Yes, but using a hash map for character counts allows efficient updates and avoids scanning each substring entirely.

What should I watch out for with k values larger than substring length?

No substrings will be valid in that case, so your code must handle k > current window size correctly.

How does fixing the left index help in this pattern?

Fixing the left index ensures substrings are counted exactly once, avoiding duplicates and simplifying frequency updates.

Is early stopping important for performance?

Yes, stopping expansion when no character can reach k prevents redundant checks and speeds up the sliding window approach.

terminal

Solution

Solution 1: Sliding Window

We can enumerate the right endpoint of the substring, and then use a sliding window to maintain the left endpoint of the substring, ensuring that the occurrence count of each character in the sliding window is less than $k$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numberOfSubstrings(self, s: str, k: int) -> int:
        cnt = Counter()
        ans = l = 0
        for c in s:
            cnt[c] += 1
            while cnt[c] >= k:
                cnt[s[l]] -= 1
                l += 1
            ans += l
        return ans

Continue Practicing

#3306 count of substrings containing every vowel and k consonants ii #3305 count of substrings containing every vowel and k consonants i #3298 count substrings that can be rearranged to contain a string ii