Maximum frequency score of a subarray

Array Hash Table Math Stack Sliding Window

36.6% acceptance

Mar 31, 2026

You are given an integer array nums and a positive integer k. The frequency score of an array is the sum of the distinct values in the array raised to the power of their frequencies, taking the sum modulo 109 + 7. For example, the frequency score of the array [5,4,5,7,4,4] is (43 + 52 + 71) modulo (109 + 7) = 96. Return the maximum frequency score of a subarray of size k in nums. You should maximize the value under the modulo and not the actual value. A subarray is a contiguous part of an array.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_frequency_score(nums: Vec<i32>, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;

    fn mod_pow(mut base: i64, mut exp: i64, modulus: i64) -> i64 {
      let mut result = 1i64;
      base %= modulus;
      while exp > 0 {
        if exp & 1 == 1 {
          result = result * base % modulus;
        }
        exp >>= 1;
        base = base * base % modulus;
      }
      result
    }

    let k = k as usize;
    let n = nums.len();
    let mut freq = std::collections::HashMap::new();
    let mut score: i64 = 0;

    // Initialize first window
    for i in 0..k {
      let v = nums[i] as i64;
      let cnt = freq.entry(nums[i]).or_insert(0i64);
      // Remove old contribution
      if *cnt > 0 {
        score = (score - mod_pow(v, *cnt, MOD) + MOD) % MOD;
      }
      *cnt += 1;
      score = (score + mod_pow(v, *cnt, MOD)) % MOD;
    }

    let mut best = score;

    // Slide window
    for i in k..n {
      // Add nums[i]
      let v = nums[i] as i64;
      let cnt = freq.entry(nums[i]).or_insert(0i64);
      if *cnt > 0 {
        score = (score - mod_pow(v, *cnt, MOD) + MOD) % MOD;
      }
      *cnt += 1;
      score = (score + mod_pow(v, *cnt, MOD)) % MOD;

      // Remove nums[i - k]
      let v = nums[i - k] as i64;
      let cnt = freq.get_mut(&nums[i - k]).unwrap();
      score = (score - mod_pow(v, *cnt, MOD) + MOD) % MOD;
      *cnt -= 1;
      if *cnt > 0 {
        score = (score + mod_pow(v, *cnt, MOD)) % MOD;
      }

      if score > best {
        best = score;
      }
    }

    best as i32
  }
}