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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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

1
2
3
4
5
6
7
8


Input: s = "abcde", k = 1

Output: 15

Explanation:

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

Constraints

  • 1 <= s.length <= 3000
  • 1 <= k <= s.length
  • s consists only of lowercase English letters.

Solution

Method 1 – Sliding Window with Frequency Counting

Intuition

For each substring, we want to check if any character appears at least k times. Since the string is not too long (≤ 3000), we can use a sliding window approach: for every possible substring, count the frequency of each character and check if any count reaches k.

Approach

  1. For every possible starting index i, initialize a frequency array of size 26 (for lowercase letters).
  2. For every ending index j ≥ i, increment the count for s[j].
  3. If any character’s count reaches k, mark the substring as valid and break (since we only need at least one such character).
  4. Count all such valid substrings.
  5. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int countSubstrings(string s, int k) {
        int n = s.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            vector<int> cnt(26, 0);
            for (int j = i; j < n; ++j) {
                cnt[s[j] - 'a']++;
                if (*max_element(cnt.begin(), cnt.end()) >= k) {
                    ans++;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

type Solution struct{}
func (Solution) CountSubstrings(s string, k int) int {
    n := len(s)
    ans := 0
    for i := 0; i < n; i++ {
        cnt := make([]int, 26)
        for j := i; j < n; j++ {
            cnt[s[j]-'a']++
            for _, v := range cnt {
                if v >= k {
                    ans++
                    break
                }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int countSubstrings(String s, int k) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; ++i) {
            int[] cnt = new int[26];
            for (int j = i; j < n; ++j) {
                cnt[s.charAt(j) - 'a']++;
                for (int v : cnt) {
                    if (v >= k) {
                        ans++;
                        break;
                    }
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun countSubstrings(s: String, k: Int): Int {
        val n = s.length
        var ans = 0
        for (i in 0 until n) {
            val cnt = IntArray(26)
            for (j in i until n) {
                cnt[s[j] - 'a']++
                if (cnt.any { it >= k }) {
                    ans++
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def countSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        ans = 0
        for i in range(n):
            cnt = [0] * 26
            for j in range(i, n):
                cnt[ord(s[j]) - ord('a')] += 1
                if max(cnt) >= k:
                    ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn count_substrings(s: String, k: i32) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut ans = 0;
        for i in 0..n {
            let mut cnt = vec![0; 26];
            for j in i..n {
                cnt[(s[j] - b'a') as usize] += 1;
                if *cnt.iter().max().unwrap() >= k {
                    ans += 1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    countSubstrings(s: string, k: number): number {
        const n = s.length;
        let ans = 0;
        for (let i = 0; i < n; ++i) {
            const cnt = Array(26).fill(0);
            for (let j = i; j < n; ++j) {
                cnt[s.charCodeAt(j) - 97]++;
                if (Math.max(...cnt) >= k) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 * 26), where n is the length of s, since we check all substrings and count frequencies.
  • 🧺 Space complexity: O(26) for the frequency array.