Count substrings with k frequency characters ii

Hash Table String Sliding Window

69.6% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_substrings(s: String, k: i32) -> i64 {
    let s = s.as_bytes();
    let n = s.len();
    let k = k as usize;
    let total = n as i64 * (n as i64 + 1) / 2;

    let mut freq = [0usize; 26];
    let mut left = 0;
    let mut less_than_k: i64 = 0;

    for right in 0..n {
      freq[(s[right] - b'a') as usize] += 1;
      while freq[(s[right] - b'a') as usize] >= k {
        freq[(s[left] - b'a') as usize] -= 1;
        left += 1;
      }
      less_than_k += (right - left + 1) as i64;
    }

    total - less_than_k
  }
}