Sum of Beauty of All Substrings solution and explanation

def beauty_sum(s: str) -> int:
    def calc_beauty(freq):
        max_freq = max(freq.values())
        min_freq = min(v for v in freq.values() if v > 0)
        return max_freq - min_freq
    
    total_beauty = 0
    n = len(s)
    for i in range(n):
        freq = {}
        for j in range(i, n):
            freq[s[j]] = freq.get(s[j], 0) + 1
            total_beauty += calc_beauty(freq)
    return total_beauty

#include <string>
#include <unordered_map>
#include <algorithm>

int beautySum(const std::string& s) {
    auto calc_beauty = [](const std::unordered_map<char, int>& freq) {
        int max_freq = 0, min_freq = INT_MAX;
        for (const auto& [char, count] : freq) {
            if (count > 0) {
                max_freq = std::max(max_freq, count);
                min_freq = std::min(min_freq, count);
            }
        }
        return max_freq - min_freq;
    };

    int total_beauty = 0;
    int n = s.length();
    for (int i = 0; i < n; ++i) {
        std::unordered_map<char, int> freq;
        for (int j = i; j < n; ++j) {
            freq[s[j]]++;
            total_beauty += calc_beauty(freq);
        }
    }
    return total_beauty;
}

def beauty_sum(s: str) -> int:
    from collections import Counter

    def calc_beauty(counter):
        max_freq = max(counter.values())
        min_freq = min(v for v in counter.values() if v > 0)
        return max_freq - min_freq

    n = len(s)
    total_beauty = 0
    prefix_freq = [Counter() for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        prefix_freq[i] = prefix_freq[i - 1].copy()
        prefix_freq[i][s[i - 1]] += 1

    for i in range(n):
        for j in range(i + 1, n + 1):
            counter = Counter({k: prefix_freq[j][k] - prefix_freq[i][k] for k in prefix_freq[j]})
            total_beauty += calc_beauty(counter)

    return total_beauty

using System;
using System.Collections.Generic;

public class Solution {
    public int BeautySum(string s) {
        int n = s.Length;
        int totalBeauty = 0;
        var prefix = new Dictionary<char, int>[n + 1];
        prefix[0] = new Dictionary<char, int>();

        for (int i = 1; i <= n; i++) {
            prefix[i] = new Dictionary<char, int>(prefix[i - 1]);
            if (!prefix[i].ContainsKey(s[i - 1]))
                prefix[i][s[i - 1]] = 0;
            prefix[i][s[i - 1]]++;
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                var freq = new Dictionary<char, int>();
                foreach (var key in prefix[j].Keys) {
                    freq[key] = prefix[j][key] - prefix[i].GetValueOrDefault(key, 0);
                }
                int maxFreq = 0, minFreq = n;
                foreach (var count in freq.Values) {
                    if (count > 0) {
                        maxFreq = Math.Max(maxFreq, count);
                        minFreq = Math.Min(minFreq, count);
                    }
                }
                totalBeauty += (maxFreq - minFreq);
            }
        }

        return totalBeauty;
    }
}

class Solution {
    public int beautySum(String s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int[] cnt = new int[26];
            for (int j = i; j < n; ++j) {
                ++cnt[s.charAt(j) - 'a'];
                int mi = 1000, mx = 0;
                for (int v : cnt) {
                    if (v > 0) {
                        mi = Math.min(mi, v);
                        mx = Math.max(mx, v);
                    }
                }
                ans += mx - mi;
            }
        }
        return ans;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var beautySum = function (s) {
    let ans = 0;
    for (let i = 0; i < s.length; ++i) {
        const cnt = new Map();
        for (let j = i; j < s.length; ++j) {
            cnt.set(s[j], (cnt.get(s[j]) || 0) + 1);
            const t = Array.from(cnt.values());
            ans += Math.max(...t) - Math.min(...t);
        }
    }
    return ans;
};

function beautySum(s: string): number {
    let ans = 0;
    for (let i = 0; i < s.length; ++i) {
        const cnt = new Map();
        for (let j = i; j < s.length; ++j) {
            cnt.set(s[j], (cnt.get(s[j]) || 0) + 1);
            const t = Array.from(cnt.values());
            ans += Math.max(...t) - Math.min(...t);
        }
    }
    return ans;
}

func beautySum(s string) (ans int) {
	for i := range s {
		cnt := [26]int{}
		for j := i; j < len(s); j++ {
			cnt[s[j]-'a']++
			mi, mx := 1000, 0
			for _, v := range cnt {
				if v > 0 {
					if mi > v {
						mi = v
					}
					if mx < v {
						mx = v
					}
				}
			}
			ans += mx - mi
		}
	}
	return
}

impl Solution {
    pub fn beauty_sum(s: String) -> i32 {
        let mut ans = 0;
        let n = s.len();
        let s: Vec<char> = s.chars().collect();

        for i in 0..n {
            let mut cnt = vec![0; 26];
            for j in i..n {
                cnt[s[j] as usize - 'a' as usize] += 1;
                let mut mi = 1000;
                let mut mx = 0;
                for &v in &cnt {
                    if v > 0 {
                        mi = mi.min(v);
                        mx = mx.max(v);
                    }
                }
                ans += mx - mi;
            }
        }
        ans
    }
}

class Solution {
    public int beautySum(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int[] cnt = new int[26];
            Map<Integer, Integer> freq = new HashMap<>();
            int mi = 1, mx = 1;
            for (int j = i; j < n; ++j) {
                int k = s.charAt(j) - 'a';
                freq.merge(cnt[k], -1, Integer::sum);
                ++cnt[k];
                freq.merge(cnt[k], 1, Integer::sum);

                if (cnt[k] == 1) {
                    mi = 1;
                }
                if (freq.getOrDefault(mi, 0) == 0) {
                    ++mi;
                }
                if (cnt[k] > mx) {
                    mx = cnt[k];
                }
                ans += mx - mi;
            }
        }
        return ans;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var beautySum = function (s) {
    const n = s.length;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        const cnt = Array(26).fill(0);
        const freq = new Map();
        let [mi, mx] = [1, 1];
        for (let j = i; j < n; ++j) {
            const k = s[j].charCodeAt() - 97;
            freq.set(cnt[k], (freq.get(cnt[k]) || 0) - 1);
            ++cnt[k];
            freq.set(cnt[k], (freq.get(cnt[k]) || 0) + 1);
            if (cnt[k] === 1) {
                mi = 1;
            }
            if (freq.get(mi) === 0) {
                ++mi;
            }
            if (cnt[k] > mx) {
                mx = cnt[k];
            }
            ans += mx - mi;
        }
    }
    return ans;
};

func beautySum(s string) (ans int) {
	n := len(s)
	for i := 0; i < n; i++ {
		cnt := [26]int{}
		freq := map[int]int{}
		mi, mx := 1, 1
		for j := i; j < n; j++ {
			k := int(s[j] - 'a')
			freq[cnt[k]]--
			cnt[k]++
			freq[cnt[k]]++

			if cnt[k] == 1 {
				mi = 1
			}
			if freq[mi] == 0 {
				mi++
			}
			if cnt[k] > mx {
				mx = cnt[k]
			}
			ans += mx - mi
		}
	}
	return
}