Maximum number of occurrences of a substring

Hash Table String Sliding Window

54.3% acceptance

Feb 25, 2026

1235

426

Given a string s, return the maximum number of occurrences of any substring under the following rules: The number of unique characters in the substring must be less than or equal to maxLetters. The substring size must be between minSize and maxSize inclusive.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_freq(s: String, max_letters: i32, min_size: i32, _max_size: i32) -> i32 {
    // Key insight: only check substrings of minSize length
    // A longer substring can only have fewer or equal occurrences than one of its substrings
    use std::collections::HashMap;
    let s = s.as_bytes();
    let n = s.len();
    let sz = min_size as usize;
    let ml = max_letters as usize;
    let mut freq_map: HashMap<&[u8], i32> = HashMap::new();
    let mut max_count = 0;

    for i in 0..=(n - sz) {
      let sub = &s[i..i + sz];
      // Count unique chars
      let mut seen = [false; 26];
      let mut unique = 0;
      for &b in sub {
        let idx = (b - b'a') as usize;
        if !seen[idx] {
          seen[idx] = true;
          unique += 1;
        }
      }
      if unique <= ml {
        let cnt = freq_map.entry(sub).or_insert(0);
        *cnt += 1;
        if *cnt > max_count { max_count = *cnt; }
      }
    }
    max_count
  }
}