Count substrings with k frequency characters i

Hash Table String Sliding Window

55.7% acceptance

Feb 23, 2026

149

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) -> i32 {
    let s = s.as_bytes();
    let n = s.len();
    let k = k as usize;
    let mut count = 0;
    
    // For each left boundary, find the smallest right where some char count >= k
    let mut freq = [0usize; 26];
    let mut left = 0;
    
    for right in 0..n {
      freq[(s[right] - b'a') as usize] += 1;
      // Shrink window from left while valid (at least one char >= k)
      while freq.iter().any(|&c| c >= k) {
        count += n - right;
        freq[(s[left] - b'a') as usize] -= 1;
        left += 1;
      }
    }
    count as i32
  }
}