Sum of beauty of all substrings

Hash Table String Counting

73.6% acceptance

Feb 25, 2026

1560

222

The beauty of a string is the difference in frequencies between the most frequent and least frequent characters. Given a string s, return the sum of beauty of all of its substrings.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn beauty_sum(s: String) -> i32 {
    let s = s.as_bytes();
    let n = s.len();
    let mut total = 0i32;
    for i in 0..n {
      let mut freq = [0i32; 26];
      for j in i..n {
        freq[(s[j] - b'a') as usize] += 1;
        let mx = *freq.iter().max().unwrap();
        let mn = freq.iter().filter(|&&x| x > 0).min().copied().unwrap();
        total += mx - mn;
      }
    }
    total
  }
}