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:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4
5

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:

1
2
3
4
5

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^4
  • 1 <= count <= 3 * 10^4
  • s consists 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

  1. 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.
  2. Return total answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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).