Explorer
Data Structures & Algorithms

Calculate sum of beauty (max freq - min freq) over all substrings.

Problem Statement

The beauty of a string is the difference in frequencies between the most frequent and least frequent characters. Return the sum of beauty of all substrings of `s`.

Examples

Input: s = "aabcb"

Output: 5

Explanation: Combining the input according to Sum of Beauty of All Substrings logic yields 5.

Input: s = "aabcbaa"

Output: 17

Explanation: Combining the input according to Sum of Beauty of All Substrings logic yields 17.

Complexity

Time Complexity: O(N² * 26)

Space Complexity: O(1)

Hints

💡 Hint 1: The beauty of a string is maxFrequency - minFrequency among present characters. 💡 Hint 2: Fix starting index i and expand j to iterate over all substrings. 💡 Hint 3: Maintain character counts in a size 26 array, updating min and max frequency at each extension.

Editorial & Approach

Problem Overview & Intuition

For every starting index i, as we extend the endpoint j, we maintain an incremental 26-character frequency table. Computing max - min across non-zero counts takes O(26) = O(1) time per substring, leading to an overall O(26 * N²) time complexity.

Step-by-Step Approach

  1. Initialize totalBeauty = 0.
  2. Outer loop i from 0 to s.length - 1.
  3. Reset frequency array freq = new Array(26).fill(0).
  4. Inner loop j from i to s.length - 1:
  5. Increment freq[s.charCodeAt(j) - 97]++.
  6. Compute maxF and minF among positive entries in freq.
  7. Add maxF - minF to totalBeauty.
  8. Return totalBeauty.

Optimal Implementation (JavaScript)

function beautySum(s) {
  let totalBeauty = 0;
  for (let i = 0; i < s.length; i++) {
    const freq = new Array(26).fill(0);
    for (let j = i; j < s.length; j++) {
      freq[s.charCodeAt(j) - 97]++;
      let maxF = 0, minF = Infinity;
      for (let k = 0; k < 26; k++) {
        if (freq[k] > 0) {
          maxF = Math.max(maxF, freq[k]);
          minF = Math.min(minF, freq[k]);
        }
      }
      totalBeauty += (maxF - minF);
    }
  }
  return totalBeauty;
}

Complexity Analysis

Time Complexity O(26 * N²) — nested loop over all substrings with 26-element min/max scan.
Space Complexity O(1) — 26-element array.

Edge Cases & Corner Traps Handled

  • Substrings of length <= 2: beauty is 0 or 1.
  • All identical characters: beauty is always 0.

Sum of Beauty of All Substrings

Medium
The beauty of a string is the difference in frequencies between the most frequent and least frequent characters. Return the sum of beauty of all substrings of `s`.
Example Scenarios
1Example 1
Input: s = "aabcb"
Output: 5
Explanation:

Combining the input according to Sum of Beauty of All Substrings logic yields 5.

2Example 2
Input: s = "aabcbaa"
Output: 17
Explanation:

Combining the input according to Sum of Beauty of All Substrings logic yields 17.

Editor
Loading Editor...
s =
"aabcb"
Output:Click "Run" above to execute and verify your code here.
5