Sum of Beauty of All Substrings

medium string counter

Problem

The beauty of a string is max frequency minus min frequency over chars that actually appear. Return the sum of beauties of all substrings of s.

Inputs = "aabcb"

Output5

Substrings with beauty > 0 contribute total 5.

def beauty_sum(s):
    total = 0
    n = len(s)
    for i in range(n):
        cnt = [0] * 26
        for j in range(i, n):
            cnt[ord(s[j]) - 97] += 1
            mx = max(cnt)
            mn = min(c for c in cnt if c > 0)
            total += mx - mn
    return total

function beautySum(s) {
  let total = 0;
  for (let i = 0; i < s.length; i++) {
    const cnt = new Array(26).fill(0);
    for (let j = i; j < s.length; j++) {
      cnt[s.charCodeAt(j) - 97]++;
      let mx = 0, mn = Infinity;
      for (const c of cnt) if (c > 0) { if (c > mx) mx = c; if (c < mn) mn = c; }
      total += mx - mn;
    }
  }
  return total;
}

class Solution {
    public int beautySum(String s) {
        int total = 0, 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 mx = 0, mn = Integer.MAX_VALUE;
                for (int c : cnt) if (c > 0) { if (c > mx) mx = c; if (c < mn) mn = c; }
                total += mx - mn;
            }
        }
        return total;
    }
}

int beautySum(string s) {
    int total = 0, n = s.size();
    for (int i = 0; i < n; i++) {
        int cnt[26] = {0};
        for (int j = i; j < n; j++) {
            cnt[s[j] - 'a']++;
            int mx = 0, mn = INT_MAX;
            for (int c : cnt) if (c > 0) { mx = max(mx, c); mn = min(mn, c); }
            total += mx - mn;
        }
    }
    return total;
}

Explanation

We need the total beauty over every substring, where a substring's beauty is its most-frequent letter count minus its least-frequent letter count. The straightforward plan is to look at all substrings, but we do it cleverly so we never recount from scratch.

The outer loop fixes a start index i, and the inner loop extends the end index j one character at a time. We keep a 26-slot array cnt for the letter frequencies of the current window. Each time j moves right, we just do cnt[s[j]]++ — the previous counts are reused.

For the current window we scan the 26 buckets to find mx (largest count) and mn (smallest count among letters that actually appear), then add mx - mn to total. Reusing cnt as the window grows is what keeps this efficient.

Because every substring is some s[i..j], sweeping all i and all j covers every substring exactly once, so the running total ends up as the sum of all beauties.

Example: in "aabcb", a window like "aab" has counts a:2, b:1, so beauty is 2 - 1 = 1. Adding up every such window across all start points gives the final answer 5.

Time: O(n²·26) Space: O(26)