Count Substrings With K-Frequency Characters I solution and explanation
Google
5 more videos on this problem
Count Substrings With K-Frequency Characters I || LeetCode Weekly Contest 420 || Leetcode Solutioncodi · 0:48 · 1K views
Leetcode Weekly Contest 420 | 3325. Count Substrings With K-Frequency Characters I | CodeFodCodeFod · 14:49 · 954 views
3325. Count Substrings With K-Frequency Characters I (Leetcode Medium)Programming Live with Larry · 6:04 · 569 views
Count Substrings With K-Frequency Characters I Leetcode 3325Code Templars · 15:48 · 176 views
3325 Count Substrings With K Frequency Characters I | 2 pointer sliding windowCode-Yao · 13:25 · 106 views
Leetcode 3325 (medium) - Count Substrings with K Frequency Characters ITechStack in Motion · 5:21 · 5 views
The problem
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 <= 30001 <= k <= s.lengthsconsists 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 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.
Approach 1: Brute Force Approach
In this approach, we generate all possible substrings of the given string s. For each substring, we maintain a frequency count of characters and check if there exists at least one character with a frequency greater than or equal to k. This method is simple but not the most efficient due to its time complexity.
def count_k_frequency_substrings(s: str, k: int) -> int:
n = len(s)
count = 0
for i in range(n):
freq = [0] * 26
for j in range(i, n):
freq[ord(s[j]) - ord('a')] += 1
if any(f >= k for f in freq):
count += 1
return count
# Example use:
s = "abacb"
k = 2
print(count_k_frequency_substrings(s, k))import java.util.*;
public class Solution {
public int countKFrequencySubstrings(String s, int k) {
int n = s.length();
int count = 0;
for (int i = 0; i < n; ++i) {
int[] freq = new int[26];
for (int j = i; j < n; ++j) {
freq[s.charAt(j) - 'a']++;
for (int c = 0; c < 26; ++c) {
if (freq[c] >= k) { count++; break; }
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
String s = "abacb";
int k = 2;
System.out.println(sol.countKFrequencySubstrings(s, k));
}
}#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int countKFrequencySubstrings(string s, int k) {
int n = s.size(), count = 0;
for (int i = 0; i < n; ++i) {
vector<int> freq(26, 0);
for (int j = i; j < n; ++j) {
freq[s[j] - 'a']++;
for (int c = 0; c < 26; ++c) {
if (freq[c] >= k) { count++; break; }
}
}
}
return count;
}
};
int main() {
Solution sol;
string s = "abacb";
int k = 2;
cout << sol.countKFrequencySubstrings(s, k) << endl;
return 0;
}function countKFrequencySubstrings(s, k) {
const n = s.length;
let count = 0;
for (let i = 0; i < n; ++i) {
const freq = new Array(26).fill(0);
for (let j = i; j < n; ++j) {
freq[s.charCodeAt(j) - 97]++;
if (freq.some(f => f >= k)) {
count++;
}
}
}
return count;
}
console.log(countKFrequencySubstrings("abacb", 2));#include <stdio.h>
#include <string.h>
int countKFrequencySubstrings(char *s, int k) {
int n = strlen(s);
int count = 0;
for (int i = 0; i < n; ++i) {
int freq[26] = {0};
for (int j = i; j < n; ++j) {
freq[s[j] - 'a']++;
for (int c = 0; c < 26; ++c) {
if (freq[c] >= k) {
count++;
break;
}
}
}
}
return count;
}
int main() {
char s[] = "abacb";
int k = 2;
printf("%d\n", countKFrequencySubstrings(s, k));
return 0;
}using System;
class Solution {
public int CountKFrequencySubstrings(string s, int k) {
int n = s.Length;
int count = 0;
for (int i = 0; i < n; ++i) {
var freq = new int[26];
for (int j = i; j < n; ++j) {
freq[s[j] - 'a']++;
foreach (int f in freq) {
if (f >= k) { count++; break; }
}
}
}
return count;
}
static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.CountKFrequencySubstrings("abacb", 2));
}
}The Python implementation uses two nested loops to cover all possible substrings. The frequency of each character is tracked using an array, updating counts only when a frequency reaches or exceeds k.
Time Complexity: O(n^3), due to multiple nested loops.
Space Complexity: O(1), as the size of the frequency list remains constant.
Approach 2: Sliding Window with HashMap
This approach utilizes a sliding window technique with a hash map to effectively manage the frequency of characters in the current window (substring). The window dynamically expands and shrinks while maintaining character frequency information, allowing us to update the count of valid substrings efficiently.
def count_k_frequency_substrings(s: str, k: int) -> int:
n = len(s)
result = 0
for start in range(n):
freq_map = {}
for end in range(start, n):
char = s[end]
if char in freq_map:
freq_map[char] += 1
else:
freq_map[char] = 1
if any(freq >= k for freq in freq_map.values()):
result += 1
return result
# Example usage
s = "abacb"
k = 2
print(count_k_frequency_substrings(s, k))This Python solution utilizes a sliding window over the string s. For each starting position, it expands the window and maintains a frequency map for characters in the current substring, incrementing the result count when any character reaches a frequency ≥ k.
Time Complexity: Roughly O(n^2), depending on hash map operations
Space Complexity: O(1) considering limited variable-size growth (bounded by 26 letters).
Approach 3: 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.
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.
function numberOfSubstrings(s: string, k: number): number {
let [ans, l] = [0, 0];
const cnt: number[] = Array(26).fill(0);
for (const c of s) {
const x = c.charCodeAt(0) - 'a'.charCodeAt(0);
++cnt[x];
while (cnt[x] >= k) {
--cnt[s[l++].charCodeAt(0) - 'a'.charCodeAt(0)];
}
ans += l;
}
return ans;
}func numberOfSubstrings(s string, k int) (ans int) {
l := 0
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
for cnt[c-'a'] >= k {
cnt[s[l]-'a']--
l++
}
ans += l
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), due to multiple nested loops. |
| Sliding Window with HashMap | Time Complexity: Roughly O(n^2), depending on hash map operations |
| Sliding Window | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Frequency Count | O(n^2 * 26) | O(26) | When first reasoning about substring enumeration or validating logic on small inputs |
| Sliding Window with HashMap | O(n) | O(26) | Best general solution for large strings where efficient substring counting is required |
Frequently asked questions
Is Count Substrings With K-Frequency Characters I easy or hard?
The problem is rated Medium because it requires recognizing a sliding window counting pattern rather than brute force substring enumeration. Once the key observation about counting n - right substrings is understood, the implementation becomes straightforward.
Count Substrings With K-Frequency Characters I Python/Java solution
The typical implementation uses a sliding window with a dictionary (Python) or HashMap/array (Java). Track character frequencies, expand the right pointer, and when a frequency reaches k, count all remaining valid substrings. The same logic easily translates to C++, JavaScript, and other languages.
How to solve Count Substrings With K-Frequency Characters I in O(n)?
Maintain a sliding window with two pointers and a frequency map. Expand the right pointer and update counts. Once any character frequency reaches k, all substrings ending at or after that position are valid, so add n - right to the answer and shrink the window from the left.
What is the best approach for Count Substrings With K-Frequency Characters I?
The most efficient approach uses a sliding window with a hash map to track character frequencies. When a character count reaches k, every extension of that window to the right remains valid, so you can add multiple substrings at once. This technique reduces the complexity to O(n) time with O(26) space.
Is Count Substrings With K-Frequency Characters I asked at Google/Amazon/Meta?
Sliding window and substring frequency problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of this question test understanding of two pointers, hash maps, and efficient substring counting.
What data structure is used in Count Substrings With K-Frequency Characters I?
The main data structure is a hash map or fixed-size frequency array used to count character occurrences in the current window. It works together with the sliding window technique to update counts in constant time while moving pointers.
What is the time complexity of Count Substrings With K-Frequency Characters I?
The optimal solution runs in O(n) time using a sliding window and frequency map. Each character is added and removed from the window at most once. A brute force approach that checks all substrings takes O(n^2 * 26) time.