Minimum substring partition of equal character frequency

Hash Table String Dynamic Programming Counting

40.0% acceptance

Feb 24, 2026

176

Given a string s, you need to partition it into one or more balanced substrings. For example, if s == "ababcc" then ("abab", "c", "c"), ("ab", "abc", "c"), and ("ababcc") are all valid partitions, but ("a", "bab", "cc"), ("aba", "bc", "c"), and ("ab", "abcc") are not. Return the minimum number of substrings that you can partition s into. Note: A balanced string is a string where each character in the string occurs the same number of times.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_substrings_in_partition(s: String) -> i32 {
    let s = s.as_bytes();
    let n = s.len();
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;
    for i in 1..=n {
      let mut freq = [0i32; 26];
      let mut distinct = 0i32;
      let mut max_freq = 0i32;
      for j in (0..i).rev() {
        let c = (s[j] - b'a') as usize;
        if freq[c] == 0 {
          distinct += 1;
        }
        freq[c] += 1;
        if freq[c] > max_freq {
          max_freq = freq[c];
        }
        // balanced: all distinct chars have the same frequency
        // max_freq * distinct == substring length
        if max_freq * distinct == (i - j) as i32 && dp[j] != i32::MAX {
          dp[i] = dp[i].min(dp[j] + 1);
        }
      }
    }
    dp[n]
  }
}