Unique substrings with equal digit frequency

Hash Table String Rolling Hash Counting Hash Function

64.6% acceptance

Mar 31, 2026

104

No description available.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashSet;

impl Solution {
  pub fn equal_digit_frequency(s: String) -> i32 {
    let bytes = s.as_bytes();
    let n = bytes.len();
    let mut set: HashSet<u64> = HashSet::new();
    
    // Rolling hash to deduplicate substrings

    for i in 0..n {
      let mut freq = [0u32; 10];
      let mut distinct = 0u32;
      let mut max_freq = 0u32;
      let mut hash: u64 = 0;
      
      for j in i..n {
        let d = (bytes[j] - b'0') as usize;
        if freq[d] == 0 {
          distinct += 1;
        }
        freq[d] += 1;
        max_freq = max_freq.max(freq[d]);
        
        // Rolling hash
        hash = hash.wrapping_mul(11).wrapping_add(d as u64 + 1);
        
        // Check if all non-zero frequencies are equal
        // This is true iff distinct * max_freq == total_chars
        let total = (j - i + 1) as u32;
        if distinct * max_freq == total {
          set.insert(hash);
        }
      }
    }
    
    set.len() as i32
  }
}