Skip to main content
Talentd

Count Substrings With K-Frequency Characters II - Solution & Explanation

HardPremiumFree on FleetCodeHash TableStringSliding Window10 min read
Practice this problem

Problem Statement

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.

 

Example 1:

Input: s = "abacb", k = 2

Output: 4

Explanation:

The valid substrings are:

  • "aba" (character 'a' appears 2 times).
  • "abac" (character 'a' appears 2 times).
  • "abacb" (character 'a' appears 2 times).
  • "bacb" (character 'b' appears 2 times).

Example 2:

Input: s = "abcde", k = 1

Output: 15

Explanation:

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

 

Constraints:

  • 1 <= s.length <= 3 * 105
  • 1 <= k <= s.length
  • s consists only of lowercase English letters.

Approach Overview

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.

Solution

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.

We can use an array cnt to maintain the occurrence count of each character in the sliding window, then use a variable l to maintain the left endpoint of the sliding window, and use a variable ans to maintain the answer.

When we enumerate the right endpoint, we can add the character at the right endpoint to the sliding window, then check if the occurrence count of the character at the right endpoint in the sliding window is greater than or equal to k. If it is, we remove the character at the left endpoint from the sliding window until the occurrence count of each character in the sliding window is less than k. At this point, for substrings with left endpoints in the range [0, ..l - 1] and right endpoint r, all satisfy the problem's requirements, so we add l to the answer.

After enumeration, we return the answer.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(|\Sigma|), where \Sigma is the character set, which in this case is the set of lowercase letters, so |\Sigma| = 26.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^2)O(1)Useful for understanding the substring condition or validating logic on small inputs
Sliding Window with Frequency MapO(n)O(1)Optimal solution for large strings; processes each character once using two pointers

Video Solution

LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,307 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Substrings With K-Frequency Characters II easy or hard?
Count Substrings With K-Frequency Characters II is categorized as a hard problem because the counting logic inside the sliding window can be tricky. Recognizing when a window becomes valid and how many substrings it contributes requires careful reasoning about frequency updates and pointer movement.
Count Substrings With K-Frequency Characters II Python/Java solution
Most implementations follow the same sliding window pattern regardless of language. Maintain two pointers, update a frequency array or map for each character, and count valid substrings once a character appears k times. The logic translates directly to Python, Java, C++, Go, and TypeScript.
How to solve Count Substrings With K-Frequency Characters II in O(n)?
Traverse the string with a sliding window using two pointers. Maintain a frequency array for characters in the current window. When any character reaches frequency k, count all valid substrings ending at the current index and shrink the window from the left while maintaining the condition. Each index is processed once, giving linear complexity.
What is the best approach for Count Substrings With K-Frequency Characters II?
The most efficient solution uses a sliding window with a frequency counter. Two pointers maintain a dynamic substring while tracking character counts in a hash table or fixed array. When a character reaches frequency k, the window becomes valid and contributes multiple substrings at once. This approach runs in O(n) time and O(1) space.
Is Count Substrings With K-Frequency Characters II asked at Google/Amazon/Meta?
Substring counting and sliding window frequency problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that involve counting substrings with specific frequency constraints are common because they test understanding of two‑pointer techniques and hash maps.
What data structure is used in Count Substrings With K-Frequency Characters II?
The main data structure is a frequency map, typically implemented as a fixed-size array or hash table. It tracks how many times each character appears in the current sliding window. Combined with two pointers, this structure allows constant‑time updates while scanning the string.
What is the time complexity of Count Substrings With K-Frequency Characters II?
The optimal sliding window algorithm runs in O(n) time because each character enters and leaves the window at most once. Frequency updates and checks are constant time operations. Space complexity is O(1) since the frequency array stores counts for a fixed alphabet size.

Ready to solve this problem?

Practice Count Substrings With K-Frequency Characters II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters