Count complete substrings

Hash Table String Sliding Window

29.9% acceptance

Feb 25, 2026

258

You are given a string word and an integer k. A substring s of word is complete if: Each character in s occurs exactly k times. The difference between two adjacent characters is at most 2. Return the number of complete substrings of word.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_complete_substrings(word: String, k: i32) -> i32 {
    let bytes = word.as_bytes();
    let n = bytes.len();
    let k = k as usize;

    // Split into maximal segments where adjacent chars differ by <= 2
    let mut segments: Vec<&[u8]> = Vec::new();
    let mut start = 0;
    for i in 1..n {
      if (bytes[i] as i32 - bytes[i - 1] as i32).abs() > 2 {
        segments.push(&bytes[start..i]);
        start = i;
      }
    }
    segments.push(&bytes[start..]);

    let mut total = 0i32;

    for seg in segments {
      let m = seg.len();
      // For each number of distinct chars j (1..=26), window size = j*k
      for dist in 1usize..=26 {
        let win = dist * k;
        if win > m { break; }
        // Sliding window of size `win` over `seg`
        let mut freq = [0i32; 26];
        let mut exact_k = 0usize; // chars with freq == k
        let mut nonzero = 0usize; // chars with freq > 0

        for i in 0..m {
          let c = (seg[i] - b'a') as usize;
          if freq[c] == 0 { nonzero += 1; }
          if freq[c] == k as i32 { exact_k -= 1; }
          freq[c] += 1;
          if freq[c] == k as i32 { exact_k += 1; }

          // Remove left element if window exceeds size
          if i >= win {
            let lc = (seg[i - win] - b'a') as usize;
            if freq[lc] == k as i32 { exact_k -= 1; }
            freq[lc] -= 1;
            if freq[lc] == k as i32 { exact_k += 1; }
            if freq[lc] == 0 { nonzero -= 1; }
          }

          if i >= win - 1 && exact_k == nonzero && nonzero == dist {
            total += 1;
          }
        }
      }
    }

    total
  }
}