Count Substrings With K-Frequency Characters II

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.

Examples

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 * 10^5
• 1 <= k <= s.length
• s consists only of lowercase English letters.

Solution

Method 1 – Sliding Window with Hash Map (Optimized for Large n)

Intuition

We want to count all substrings where at least one character appears at least k times. For large n, we can fix the character and use a sliding window to efficiently count substrings where that character appears at least k times. We sum this for all 26 lowercase letters.

Approach

1. For each character 'a' to 'z':
   • Use a sliding window to find all substrings where this character appears at least k times.
   • For each right pointer, increment the count for the character.
   • When the count for the character reaches k, all substrings starting from the left pointer up to the current right pointer are valid.
   • Move the left pointer to shrink the window and continue.
2. Use a set to avoid double-counting substrings (or use a mathematical approach to count only new substrings).
3. Sum the results for all characters.
4. Return the total count.

Code

C++

class Solution {
public:
    long long countSubstrings(string s, int k) {
        int n = s.size();
        long long ans = 0;
        for (char ch = 'a'; ch <= 'z'; ++ch) {
            vector<int> cnt(26, 0);
            int l = 0, freq = 0;
            for (int r = 0; r < n; ++r) {
                cnt[s[r] - 'a']++;
                if (s[r] == ch && cnt[ch - 'a'] >= k) {
                    while (cnt[ch - 'a'] > k) {
                        cnt[s[l++] - 'a']--;
                    }
                    ans += l + 1;
                }
            }
        }
        return ans;
    }
};

Go

type Solution struct{}
func (Solution) CountSubstrings(s string, k int) int64 {
    n := len(s)
    var ans int64
    for ch := byte('a'); ch <= 'z'; ch++ {
        cnt := make([]int, 26)
        l := 0
        for r := 0; r < n; r++ {
            cnt[s[r]-'a']++
            if s[r] == ch && cnt[ch-'a'] >= k {
                for cnt[ch-'a'] > k {
                    cnt[s[l]-'a']--
                    l++
                }
                ans += int64(l + 1)
            }
        }
    }
    return ans
}

Java

class Solution {
    public long countSubstrings(String s, int k) {
        int n = s.length();
        long ans = 0;
        for (char ch = 'a'; ch <= 'z'; ++ch) {
            int[] cnt = new int[26];
            int l = 0;
            for (int r = 0; r < n; ++r) {
                cnt[s.charAt(r) - 'a']++;
                if (s.charAt(r) == ch && cnt[ch - 'a'] >= k) {
                    while (cnt[ch - 'a'] > k) {
                        cnt[s.charAt(l++) - 'a']--;
                    }
                    ans += l + 1;
                }
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun countSubstrings(s: String, k: Int): Long {
        val n = s.length
        var ans = 0L
        for (ch in 'a'..'z') {
            val cnt = IntArray(26)
            var l = 0
            for (r in 0 until n) {
                cnt[s[r] - 'a']++
                if (s[r] == ch && cnt[ch - 'a'] >= k) {
                    while (cnt[ch - 'a'] > k) {
                        cnt[s[l++] - 'a']--
                    }
                    ans += l + 1
                }
            }
        }
        return ans
    }
}

Python

class Solution:
    def countSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        ans = 0
        for ch in range(26):
            cnt = [0] * 26
            l = 0
            for r in range(n):
                cnt[ord(s[r]) - ord('a')] += 1
                if ord(s[r]) - ord('a') == ch and cnt[ch] >= k:
                    while cnt[ch] > k:
                        cnt[ord(s[l]) - ord('a')] -= 1
                        l += 1
                    ans += l + 1
        return ans

Rust

impl Solution {
    pub fn count_substrings(s: String, k: i32) -> i64 {
        let n = s.len();
        let s = s.as_bytes();
        let mut ans = 0i64;
        for ch in b'a'..=b'z' {
            let mut cnt = vec![0; 26];
            let mut l = 0;
            for r in 0..n {
                cnt[(s[r] - b'a') as usize] += 1;
                if s[r] == ch && cnt[(ch - b'a') as usize] >= k {
                    while cnt[(ch - b'a') as usize] > k {
                        cnt[(s[l] - b'a') as usize] -= 1;
                        l += 1;
                    }
                    ans += (l + 1) as i64;
                }
            }
        }
        ans
    }
}

TypeScript

class Solution {
    countSubstrings(s: string, k: number): number {
        const n = s.length;
        let ans = 0;
        for (let ch = 0; ch < 26; ++ch) {
            const cnt = Array(26).fill(0);
            let l = 0;
            for (let r = 0; r < n; ++r) {
                cnt[s.charCodeAt(r) - 97]++;
                if (s.charCodeAt(r) - 97 === ch && cnt[ch] >= k) {
                    while (cnt[ch] > k) {
                        cnt[s.charCodeAt(l) - 97]--;
                        l++;
                    }
                    ans += l + 1;
                }
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(26 * n), where n is the length of s, since we process each character for each letter.
• 🧺 Space complexity: O(26) for the frequency array.