☕ DSA Java Articles

Topics › Strings › Medium String Problems

Sum of Beauty of All Substrings

Medium TUF ID 993 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

The beauty of a string is the difference between the frequency of its most frequent character and the frequency of its least frequent character, counting only characters that actually appear. For example "abaacc" has frequencies a = 3, b = 1, c = 2, so its beauty is 3 - 1 = 2. A string in which every present character occurs equally often has beauty 0.

Given a string s of lowercase letters, return the sum of the beauties of all of its substrings.

Constraints: 1 ≤ |s| ≤ 500; lowercase English letters only.

Example 1

s = "aabcb"
answer = 5              // "aab", "aabc", "aabcb", "abcb", "bcb" each have beauty 1; every other substring has beauty 0

Example 2

s = "aabcbaa"
answer = 17

Example 3

s = "aaaa"
answer = 0              // one distinct letter: max and min frequency always coincide

Approach 1: Brute force, count every substring from scratch

Intuition. Enumerate every substring s[i..j], build its 26-slot frequency table by scanning it, then find the largest and smallest non-zero entries. There is nothing clever here, but it gives us a reference implementation that the faster methods are tested against in main.

Algorithm.

  1. For every start i and end j ≥ i:
  2. Count the letters of s[i..j] into freq[26].
  3. Add beauty(freq), the difference between the maximum and the minimum non-zero count, to the total.
static long bruteForce(String s) {
    int n = s.length();
    long total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int[] freq = new int[26];
            for (int p = i; p <= j; p++) freq[s.charAt(p) - 'a']++;
            total += beauty(freq);
        }
    }
    return total;
}

private static int beauty(int[] freq) {
    int max = 0, min = Integer.MAX_VALUE;
    for (int f : freq) {
        if (f == 0) continue;
        if (f > max) max = f;
        if (f < min) min = f;
    }
    return max == 0 ? 0 : max - min;
}

Complexity. Time O(n^3): O(n^2) substrings, each scanned in O(n) plus a constant 26-slot pass. Space O(1).

Note the guard in beauty: the minimum must ignore letters with count 0, otherwise every substring that misses at least one letter of the alphabet would get a minimum of 0 and the “beauty” would just be the maximum frequency.

Approach 2: Better, extend the end and keep the table

Intuition. Fix the start i. The substrings s[i..i], s[i..i+1], s[i..i+2], and so on each differ from the previous one by exactly one appended letter. So the frequency table does not need rebuilding: increment one slot per step. The max and min are then recomputed with a pass over the 26 slots. That pass is constant work, and the O(n) rebuild disappears.

Algorithm.

  1. For every start i: clear freq[26].
  2. For j from i to n - 1: freq[s[j]]++, then add beauty(freq) to the total.
static long better(String s) {
    int n = s.length();
    long total = 0;
    for (int i = 0; i < n; i++) {
        int[] freq = new int[26];
        for (int j = i; j < n; j++) {
            freq[s.charAt(j) - 'a']++;
            total += beauty(freq);
        }
    }
    return total;
}

Complexity. Time O(26 · n^2), about 3.3 × 10^6 elementary steps for n = 500. Space O(1).

For the given constraints this already runs in a few milliseconds, and many accepted solutions stop here. The remaining factor of 26 is a constant, but it is a constant that depends on the alphabet, and the next approach shows how to remove it.

Approach 3: Optimal, maintain the max and min incrementally

Intuition. While the end j grows, every frequency in the table can only go up. That has two consequences.

The maximum is trivial: it is max(maxF, newCount) after each increment, because the letter we just touched is the only one that changed.

The minimum needs one extra piece of information: how many letters currently sit at each frequency. Call it lettersWith[f]. When the letter c goes from frequency f to f + 1, two things can happen to the minimum:

Because frequencies never decrease within the inner loop, the minimum never has to be searched for; it only ever resets to 1 or steps up by one. Each update is O(1).

Algorithm.

  1. For every start i: clear freq[26] and lettersWith[0..n+1]; set maxF = minF = 0.
  2. For j from i to n - 1, with c = s[j] and f = freq[c]:
    • If f > 0, decrement lettersWith[f]. Set freq[c] = f + 1 and increment lettersWith[f + 1].
    • maxF = max(maxF, f + 1).
    • If f == 0, set minF = 1; else if f == minF and lettersWith[f] == 0, set minF = f + 1.
    • Add maxF - minF to the total.
static long optimal(String s) {
    int n = s.length();
    long total = 0;
    for (int i = 0; i < n; i++) {
        int[] freq = new int[26];
        int[] lettersWith = new int[n + 2];            // lettersWith[f] = how many letters occur exactly f times
        int maxF = 0, minF = 0;
        for (int j = i; j < n; j++) {
            int c = s.charAt(j) - 'a';
            int f = freq[c];                           // old frequency of this letter
            if (f > 0) lettersWith[f]--;
            freq[c] = f + 1;
            lettersWith[f + 1]++;
            if (f + 1 > maxF) maxF = f + 1;
            if (f == 0) minF = 1;                      // a letter seen for the first time is the rarest
            else if (f == minF && lettersWith[f] == 0) minF = f + 1;
            total += maxF - minF;
        }
    }
    return total;
}

Dry run for the start i = 0 of s = "aabcb":

j letter old f freq after lettersWith (non-zero) maxF minF beauty
0 a 0 a=1 [1]=1 1 1 0
1 a 1 a=2 [2]=1 2 2 (nothing left at 1) 0
2 b 0 a=2, b=1 [1]=1, [2]=1 2 1 (new letter) 1
3 c 0 a=2, b=1, c=1 [1]=2, [2]=1 2 1 1
4 b 1 a=2, b=2, c=1 [1]=1, [2]=2 2 1 (c still at 1) 1

The start i = 0 contributes 3. The starts i = 1 ("abcb" → 1) and i = 2 ("bcb" → 1) add 2 more, and i = 3, 4 add nothing, for a total of 5.

Complexity. Time O(n^2): n(n + 1) / 2 substrings, constant work each. Space O(n) for lettersWith, which has to hold frequencies up to n.

Edge cases and pitfalls