Sum of Beauty of All Substrings

Medium
1752.

Sum of Beauty of All Substrings

Sum of Beauty of All Substrings is a medium coding problem on strings, hash table and counting, asked in Amazon and Google interviews.

The beauty of a string is the difference between the number of times its most frequent character appears and the number of times its least frequent character appears — counting only characters that do appear.

For example, the beauty of "abaacc" is 3 - 1 = 2 (a appears three times, b once).

Given a string s, return the sum of the beauty of all of its substrings.

Example 1

Input
s = "kaaik"
Output
5
Explanation
`"kaa"`, `"kaai"`, `"kaaik"`, `"aai"` and `"aaik"` each have beauty 1; every other substring has beauty 0.

Example 2

Input
s = "abcab"
Output
3
Explanation
`"abca"`, `"bcab"` and `"abcab"` have beauty 1.

Example 3

Input
s = "zz"
Output
0

Constraints

  • 1 <= s.length <= 500
  • s consists of only lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var beautySum = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sum of Beauty of All Substrings — Problem & Solution

Sum of Beauty of All Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Sum of Beauty of All Substrings is a medium coding problem on strings, hash table and counting, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Counting
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The beauty of a string is the difference between the number of times its most frequent character appears and the number of times its least frequent character appears — counting only characters that do appear.

For example, the beauty of "abaacc" is 3 - 1 = 2 (a appears three times, b once).

Given a string s, return the sum of the beauty of all of its substrings.

Example 1

Input: s = "kaaik"
Output: 5
Explanation: `"kaa"`, `"kaai"`, `"kaaik"`, `"aai"` and `"aaik"` each have beauty 1; every other substring has beauty 0.

Example 2

Input: s = "abcab"
Output: 3
Explanation: `"abca"`, `"bcab"` and `"abcab"` have beauty 1.

Example 3

Input: s = "zz"
Output: 0

Constraints

  • 1 <= s.length <= 500
  • s consists of only lowercase English letters

Hints for Sum of Beauty of All Substrings

  1. Hint 1

    There are about n^2 / 2 substrings — with n <= 500 you can afford to look at every one, but not to recount each from scratch.

  2. Hint 2

    Fix the start i and extend the end j one character at a time, updating a 26-entry count array.

  3. Hint 3

    After each extension, the beauty is the max count minus the smallest non-zero count — a 26-step scan.

How to solve Sum of Beauty of All Substrings

Enumerate substrings by start and end, maintaining character counts incrementally so each substring costs only a scan of the 26 counters.

Approach

  1. For each start i, reset a 26-entry count array.
  2. For each end j >= i, increment the count of s[j].
  3. Scan the counts: the largest value minus the smallest non-zero value is this substring's beauty; add it to the total.

Why it works

Every substring is s[i..j] for exactly one pair i <= j, and the count array after processing j holds exactly the frequencies of s[i..j].

Complexity

  • Time — O(26 · n^2)
  • Space — O(26)

Pitfalls

  • The minimum ignores letters with count 0 — otherwise every substring missing a letter would look beautiful.
  • Recounting each substring from scratch is O(n^3).

Reference solution

Python

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

Java

public static int beautySum(String s) {
    int n = s.length(), total = 0;
    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 v : cnt) {
                if (v == 0) continue;
                mx = Math.max(mx, v);
                mn = Math.min(mn, v);
            }
            total += mx - mn;
        }
    }
    return total;
}

C++

int beautySum(string s) {
    int n = s.size(), total = 0;
    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 v : cnt) {
                if (v == 0) continue;
                mx = max(mx, v);
                mn = min(mn, v);
            }
            total += mx - mn;
        }
    }
    return total;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets