Number of equal count substrings

Hash Table String Sliding Window Counting

45.4% acceptance

Mar 31, 2026

111

No description available.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn equal_count_substrings(s: String, count: i32) -> i32 {
    let count = count as usize;
    let bytes = s.as_bytes();
    let n = bytes.len();
    let mut result = 0;

    // For each possible number of unique characters (1..=26)
    for unique in 1..=26usize {
      let window = unique * count;
      if window > n {
        break;
      }
      let mut freq = [0usize; 26];
      let mut valid = 0usize; // number of chars with exactly count occurrences

      for i in 0..n {
        let ci = (bytes[i] - b'a') as usize;
        if freq[ci] == count {
          valid -= 1;
        }
        freq[ci] += 1;
        if freq[ci] == count {
          valid += 1;
        }

        if i >= window {
          let cj = (bytes[i - window] - b'a') as usize;
          if freq[cj] == count {
            valid -= 1;
          }
          freq[cj] -= 1;
          if freq[cj] == count {
            valid += 1;
          }
        }

        if i + 1 >= window && valid == unique {
          result += 1;
        }
      }
    }

    result
  }
}