Problem Description

The problem asks us to find the sum of beauty values for all possible substrings of a given string s.

The beauty of a string is defined as the difference between the frequency of the most frequent character and the frequency of the least frequent character in that string.

For example, in the string "abaacc":

• Character 'a' appears 3 times (most frequent)
• Character 'b' appears 1 time (least frequent)
• Character 'c' appears 2 times
• Beauty = 3 - 1 = 2

The task is to:

1. Find all possible substrings of the input string s
2. Calculate the beauty value for each substring
3. Return the sum of all these beauty values

The solution uses a nested loop approach where:

• The outer loop (variable i) marks the starting position of each substring
• The inner loop (variable j) extends from position i to the end of the string, considering all substrings starting at position i
• A counter tracks the frequency of each character as we extend the substring
• For each substring formed, we calculate its beauty by finding the difference between the maximum and minimum frequency values
• All beauty values are accumulated and returned as the final answer

Intuition

The key insight is that we need to examine every possible substring of the given string to calculate its beauty value. Since we need all substrings, a brute force approach makes sense here.

Think about how substrings are formed - any substring can be defined by two positions: a starting index and an ending index. This naturally leads to a nested loop structure where we fix a starting position and then explore all possible ending positions from that start.

Why do we build substrings incrementally? Instead of generating each substring from scratch and counting its character frequencies separately, we can be more efficient. When we extend a substring by one character (moving from substring s[i:j] to s[i:j+1]), we only need to update our frequency count for that one new character. This allows us to maintain a running frequency counter that gets updated as we extend the substring.

The beauty calculation becomes straightforward once we have the frequency counts. At each step, after adding a new character to our current substring, we can immediately calculate the beauty by finding the difference between max(cnt.values()) and min(cnt.values()). This gives us the beauty of the current substring s[i:j+1].

The approach essentially answers: "For each possible starting position, what are all the substrings I can form, and what is their beauty?" By systematically exploring all starting positions (outer loop) and all ending positions from each start (inner loop), we ensure we don't miss any substring.

Solution Approach

The solution uses an enumeration approach with counting to solve the problem efficiently.

We enumerate each starting position i in the string, treating it as the left endpoint of our substrings. For each starting position, we find all substrings that begin at this position by extending to different ending positions.

The implementation follows these steps:

1. Initialize variables: Set ans = 0 to store the total beauty sum and n = len(s) to get the string length.

2. Outer loop - Fix starting position: Iterate through each index i from 0 to n-1. This represents the starting position of our substrings.

3. Initialize counter for each starting position: Create a new Counter() object (a dictionary that tracks character frequencies) for each starting position. This counter will be reused and updated as we extend the substring.

4. Inner loop - Extend substring: For each starting position i, iterate j from i to n-1. This represents the ending position of the substring s[i:j+1].

5. Update frequency count: Add the character at position j to our counter: cnt[s[j]] += 1. This incrementally builds the frequency map as we extend the substring.

6. Calculate and accumulate beauty: After adding each new character, calculate the beauty of the current substring as max(cnt.values()) - min(cnt.values()) and add it to our answer.

7. Return result: After processing all possible substrings, return the accumulated sum.

The time complexity is O(n² × k) where n is the length of the string and k is the number of unique characters in each substring (for finding max and min values). The space complexity is O(k) for the counter, where k is at most 26 for lowercase English letters.

Example Walkthrough

Let's walk through the solution with a small example: s = "aab"

Step 1: Initialize

• ans = 0 (to accumulate total beauty)
• n = 3 (length of string)

Step 2: Process starting position i = 0

Initialize cnt = Counter() for substrings starting at index 0.

• j = 0: Substring is "a"

  • Update: cnt['a'] = 1
  • Frequencies: {'a': 1}
  • Beauty = max(1) - min(1) = 0
  • ans = 0 + 0 = 0

• j = 1: Substring is "aa"

  • Update: cnt['a'] = 2
  • Frequencies: {'a': 2}
  • Beauty = max(2) - min(2) = 0
  • ans = 0 + 0 = 0

• j = 2: Substring is "aab"

  • Update: cnt['b'] = 1
  • Frequencies: {'a': 2, 'b': 1}
  • Beauty = max(2, 1) - min(2, 1) = 2 - 1 = 1
  • ans = 0 + 1 = 1

Step 3: Process starting position i = 1

Initialize new cnt = Counter() for substrings starting at index 1.

• j = 1: Substring is "a"

  • Update: cnt['a'] = 1
  • Frequencies: {'a': 1}
  • Beauty = max(1) - min(1) = 0
  • ans = 1 + 0 = 1

• j = 2: Substring is "ab"

  • Update: cnt['b'] = 1
  • Frequencies: {'a': 1, 'b': 1}
  • Beauty = max(1, 1) - min(1, 1) = 1 - 1 = 0
  • ans = 1 + 0 = 1

Step 4: Process starting position i = 2

Initialize new cnt = Counter() for substrings starting at index 2.

• j = 2: Substring is "b"
  • Update: cnt['b'] = 1
  • Frequencies: {'b': 1}
  • Beauty = max(1) - min(1) = 0
  • ans = 1 + 0 = 1

Final Result: The sum of all beauty values is 1.

The key insight demonstrated here is how we incrementally build each substring by extending it one character at a time, updating our frequency counter as we go, rather than recalculating frequencies from scratch for each substring.

Solution Implementation

Time and Space Complexity

The time complexity is O(n² × C), where n is the length of the string and C is the size of the character set (26 for lowercase English letters).

• The outer loop runs n times (from i = 0 to n-1)
• The inner loop runs n-i times for each iteration of the outer loop
• Total iterations: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)
• Inside the inner loop, finding max(cnt.values()) and min(cnt.values()) each takes O(C) time since we need to iterate through all character counts in the Counter
• Therefore, the overall time complexity is O(n² × C)

The space complexity is O(C), where C = 26.

• The Counter object cnt stores at most C distinct characters (26 lowercase English letters)
• Even though we create a new Counter for each starting position i, we only maintain one Counter at a time
• The space used by the Counter is bounded by the size of the character set, not the length of the string

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Max/Min Calculation for Every Substring

The current solution calls max(char_frequency.values()) and min(char_frequency.values()) for every substring, which iterates through all frequency values each time. This becomes inefficient when dealing with longer strings.

Why it's a problem: For each substring s[i:j+1], we're iterating through up to 26 values (for lowercase English letters) to find max and min. With O(n²) substrings, this adds unnecessary overhead.

Better approach: Track max and min frequencies incrementally or use a more efficient data structure:

from collections import Counter, defaultdict

class Solution:
    def beautySum(self, s: str) -> int:
        total_beauty = 0
        n = len(s)
      
        for i in range(n):
            char_freq = defaultdict(int)
            freq_count = defaultdict(int)  # Track how many chars have each frequency
            max_freq = 0
          
            for j in range(i, n):
                char = s[j]
                old_freq = char_freq[char]
                new_freq = old_freq + 1
                char_freq[char] = new_freq
              
                # Update frequency tracking
                if old_freq > 0:
                    freq_count[old_freq] -= 1
                    if freq_count[old_freq] == 0:
                        del freq_count[old_freq]
                freq_count[new_freq] += 1
              
                # Update max frequency
                max_freq = max(max_freq, new_freq)
              
                # Find min frequency (smallest key in freq_count)
                if freq_count:
                    min_freq = min(freq_count.keys())
                    total_beauty += max_freq - min_freq
      
        return total_beauty

2. Unnecessary Beauty Calculation for Single Character Substrings

When start_index == end_index, the substring contains only one character, so all frequencies are 1, making beauty = 1 - 1 = 0. These calculations don't contribute to the sum but still consume resources.

Optimization: Skip beauty calculation for single-character substrings:

for end_index in range(start_index, string_length):
    char_frequency[s[end_index]] += 1
  
    # Skip single character substrings (beauty is always 0)
    if end_index > start_index:
        max_frequency = max(char_frequency.values())
        min_frequency = min(char_frequency.values())
        total_beauty += max_frequency - min_frequency

3. Memory Overhead from Counter Object Creation

Creating a new Counter() object for each starting position can cause memory allocation overhead, especially for large strings.

Alternative: Reuse a single dictionary and reset it manually:

char_frequency = {}
for start_index in range(string_length):
    char_frequency.clear()  # Reset for new starting position
  
    for end_index in range(start_index, string_length):
        char = s[end_index]
        char_frequency[char] = char_frequency.get(char, 0) + 1
        # ... rest of logic

4. Missing Early Termination Opportunities

The algorithm doesn't leverage the fact that beauty can only increase or stay the same as we extend a substring (max can only increase or stay same, min can only decrease or stay same).

Potential optimization: Track when beauty values stabilize for certain patterns, though this is more complex to implement correctly and may not always provide significant benefits.