Minimum operations to make character frequencies equal

Hash Table String Dynamic Programming Counting Enumeration

26.4% acceptance

Feb 24, 2026

You are given a string s. A string t is called good if all characters of t occur the same number of times. You can perform the following operations any number of times: Delete a character from s. Insert a character in s. Change a character in s to its next letter in the alphabet. Note that you cannot change 'z' to 'a' using the third operation. Return the minimum number of operations required to make s good.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn make_string_good(s: String) -> i32 {
    let mut freq = [0i32; 26];
    for b in s.bytes() {
      freq[(b - b'a') as usize] += 1;
    }

    // For each target T every letter ends up with count 0 or T.
    // DP processes letters a-z left-to-right with state = carry (chars
    // forwarded to the next letter via "change" operations, each costing 1).
    //   available = freq[i] + carry
    //
    //   available == 0              → carry_out = 0, cost += 0
    //   available >= T  (surplus)   → cost += surplus
    //       carry_out ∈ {0, clamp(crossover, 0, max_push), max_push}
    //       where crossover = max(0, T − freq[i+1])   (fills i+1 exactly)
    //             max_push  = min(surplus, T)
    //   available < T   (deficit)   →
    //       a) insert: carry_out = 0,  cost += T − available
    //       b) spend:  carry_out ∈ {0, clamp(crossover, 0, available), available}
    //                  cost += available
    //
    // Trying only ≤3 carry values per transition (instead of the full O(T)
    // range) is correct: intermediate values are dominated by one of the
    // three representative points (zero, exact-fill, maximum).  By keeping
    // the DP as a sparse HashMap<carry → min_cost> the active state count
    // stays O(1) throughout, making each target O(26) work and the total
    // algorithm O(26 · max_freq) ≈ O(n).

    let max_freq = *freq.iter().max().unwrap();
    if max_freq == 0 { return 0; }
    let mut ans = s.len() as i32;

    for target in 1..=(max_freq + 1) {
      let mut dp: std::collections::HashMap<i32, i32> = std::collections::HashMap::new();
      dp.insert(0, 0);

      for i in 0..26usize {
        let f = freq[i];
        let next_f = if i < 25 { freq[i + 1] } else { 0 };
        let crossover = (target - next_f).max(0);

        let mut ndp: std::collections::HashMap<i32, i32> = std::collections::HashMap::new();
        let upd = |m: &mut std::collections::HashMap<i32, i32>, k: i32, v: i32| {
          let e = m.entry(k).or_insert(i32::MAX);
          if v < *e { *e = v; }
        };

        for (&carry, &cost) in &dp {
          let available = f + carry;
          if available == 0 {
            upd(&mut ndp, 0, cost);
          } else if available >= target {
            let surplus  = available - target;
            let max_push = if i < 25 { surplus.min(target) } else { 0 };
            let c_cross  = crossover.min(max_push);
            upd(&mut ndp, 0,       cost + surplus);
            upd(&mut ndp, c_cross, cost + surplus);
            upd(&mut ndp, max_push, cost + surplus);
          } else {
            // (a) insert
            upd(&mut ndp, 0, cost + (target - available));
            // (b) spend
            let max_k   = if i < 25 { available } else { 0 };
            let c_cross = crossover.min(max_k);
            upd(&mut ndp, 0,      cost + available);
            upd(&mut ndp, c_cross, cost + available);
            upd(&mut ndp, max_k,  cost + available);
          }
        }
        dp = ndp;
      }

      let best = dp.iter()
        .map(|(&c, &cost)| cost + c)
        .min()
        .unwrap_or(s.len() as i32);
      if best < ans { ans = best; }
    }

    ans
  }
}