Number of Equal Count Substrings
MediumUpdated: Aug 2, 2025
Practice on:
Problem
You are given a 0-indexed string s consisting of only lowercase English letters, and an integer count. A substring of s is said to be an
equal count substring if, for each unique letter in the substring, it appears exactly count times in the substring.
Return _the number ofequal count substrings in _s.
A substring is a contiguous non-empty sequence of characters within a string.
Examples
Example 1:
Input: s = "aaabcbbcc", count = 3
Output: 3
Explanation:
The substring that starts at index 0 and ends at index 2 is "aaa".
The letter 'a' in the substring appears exactly 3 times.
The substring that starts at index 3 and ends at index 8 is "bcbbcc".
The letters 'b' and 'c' in the substring appear exactly 3 times.
The substring that starts at index 0 and ends at index 8 is "aaabcbbcc".
The letters 'a', 'b', and 'c' in the substring appear exactly 3 times.
Example 2:
Input: s = "abcd", count = 2
Output: 0
Explanation:
The number of times each letter appears in s is less than count.
Therefore, no substrings in s are equal count substrings, so return 0.
Example 3:
Input: s = "a", count = 5
Output: 0
Explanation:
The number of times each letter appears in s is less than count.
Therefore, no substrings in s are equal count substrings, so return 0
Constraints:
1 <= s.length <= 3 * 10^41 <= count <= 3 * 10^4sconsists only of lowercase English letters.
Solution
Method 1 – Sliding Window with Frequency Count
Intuition
For each possible number of unique letters, try all windows of size unique*count. For each window, check if all letters appear exactly count times.
Approach
- For unique in 1..26:
- Window size = unique * count
- Use a sliding window to count frequencies in each window.
- If all nonzero frequencies are exactly count, increment answer.
- Return total answer.
Code
C++
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
int equalCountSubstrings(string s, int count) {
int n = s.size(), ans = 0;
for (int unique = 1; unique <= 26; ++unique) {
int len = unique * count;
if (len > n) break;
vector<int> freq(26, 0);
int diff = 0;
for (int i = 0; i < len; ++i) {
int idx = s[i]-'a';
if (freq[idx] == 0) diff++;
freq[idx]++;
}
if (diff == unique && all_of(freq.begin(), freq.end(), [&](int f){ return f == 0 || f == count; })) ans++;
for (int i = len; i < n; ++i) {
int out = s[i-len]-'a', in = s[i]-'a';
freq[out]--;
if (freq[out] == 0) diff--;
if (freq[in] == 0) diff++;
freq[in]++;
if (diff == unique && all_of(freq.begin(), freq.end(), [&](int f){ return f == 0 || f == count; })) ans++;
}
}
return ans;
}
};
Go
func equalCountSubstrings(s string, count int) int {
n, ans := len(s), 0
for unique := 1; unique <= 26; unique++ {
length := unique * count
if length > n { break }
freq := make([]int, 26)
diff := 0
for i := 0; i < length; i++ {
idx := s[i] - 'a'
if freq[idx] == 0 { diff++ }
freq[idx]++
}
if diff == unique && check(freq, count) { ans++ }
for i := length; i < n; i++ {
out, in := s[i-length]-'a', s[i]-'a'
freq[out]--
if freq[out] == 0 { diff-- }
if freq[in] == 0 { diff++ }
freq[in]++
if diff == unique && check(freq, count) { ans++ }
}
}
return ans
}
func check(freq []int, count int) bool {
for _, f := range freq {
if f != 0 && f != count { return false }
}
return true
}
Java
class Solution {
public int equalCountSubstrings(String s, int count) {
int n = s.length(), ans = 0;
for (int unique = 1; unique <= 26; ++unique) {
int len = unique * count;
if (len > n) break;
int[] freq = new int[26];
int diff = 0;
for (int i = 0; i < len; ++i) {
int idx = s.charAt(i)-'a';
if (freq[idx] == 0) diff++;
freq[idx]++;
}
if (diff == unique && check(freq, count)) ans++;
for (int i = len; i < n; ++i) {
int out = s.charAt(i-len)-'a', in = s.charAt(i)-'a';
freq[out]--;
if (freq[out] == 0) diff--;
if (freq[in] == 0) diff++;
freq[in]++;
if (diff == unique && check(freq, count)) ans++;
}
}
return ans;
}
boolean check(int[] freq, int count) {
for (int f : freq) if (f != 0 && f != count) return false;
return true;
}
}
Kotlin
class Solution {
fun equalCountSubstrings(s: String, count: Int): Int {
val n = s.length
var ans = 0
for (unique in 1..26) {
val len = unique * count
if (len > n) break
val freq = IntArray(26)
var diff = 0
for (i in 0 until len) {
val idx = s[i]-'a'
if (freq[idx] == 0) diff++
freq[idx]++
}
if (diff == unique && freq.all { it == 0 || it == count }) ans++
for (i in len until n) {
val out = s[i-len]-'a'; val inx = s[i]-'a'
freq[out]--
if (freq[out] == 0) diff--
if (freq[inx] == 0) diff++
freq[inx]++
if (diff == unique && freq.all { it == 0 || it == count }) ans++
}
}
return ans
}
}
Python
class Solution:
def equalCountSubstrings(self, s: str, count: int) -> int:
n, ans = len(s), 0
for unique in range(1, 27):
length = unique * count
if length > n: break
freq = [0]*26
diff = 0
for i in range(length):
idx = ord(s[i])-ord('a')
if freq[idx] == 0: diff += 1
freq[idx] += 1
if diff == unique and all(f == 0 or f == count for f in freq): ans += 1
for i in range(length, n):
out, inx = ord(s[i-length])-ord('a'), ord(s[i])-ord('a')
freq[out] -= 1
if freq[out] == 0: diff -= 1
if freq[inx] == 0: diff += 1
freq[inx] += 1
if diff == unique and all(f == 0 or f == count for f in freq): ans += 1
return ans
Rust
impl Solution {
pub fn equal_count_substrings(s: String, count: i32) -> i32 {
let n = s.len();
let s = s.as_bytes();
let mut ans = 0;
for unique in 1..=26 {
let len = unique * count as usize;
if len > n { break; }
let mut freq = vec![0; 26];
let mut diff = 0;
for i in 0..len {
let idx = (s[i]-b'a') as usize;
if freq[idx] == 0 { diff += 1; }
freq[idx] += 1;
}
if diff == unique && freq.iter().all(|&f| f == 0 || f == count) { ans += 1; }
for i in len..n {
let out = (s[i-len]-b'a') as usize;
let inx = (s[i]-b'a') as usize;
freq[out] -= 1;
if freq[out] == 0 { diff -= 1; }
if freq[inx] == 0 { diff += 1; }
freq[inx] += 1;
if diff == unique && freq.iter().all(|&f| f == 0 || f == count) { ans += 1; }
}
}
ans
}
}
TypeScript
class Solution {
equalCountSubstrings(s: string, count: number): number {
const n = s.length;
let ans = 0;
for (let unique = 1; unique <= 26; ++unique) {
const len = unique * count;
if (len > n) break;
const freq = Array(26).fill(0);
let diff = 0;
for (let i = 0; i < len; ++i) {
const idx = s.charCodeAt(i)-97;
if (freq[idx] === 0) diff++;
freq[idx]++;
}
if (diff === unique && freq.every(f => f === 0 || f === count)) ans++;
for (let i = len; i < n; ++i) {
const out = s.charCodeAt(i-len)-97, inx = s.charCodeAt(i)-97;
freq[out]--;
if (freq[out] === 0) diff--;
if (freq[inx] === 0) diff++;
freq[inx]++;
if (diff === unique && freq.every(f => f === 0 || f === count)) ans++;
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(26*n), where n is the length of s. - 🧺 Space complexity:
O(26).