Sum of Beauty of All Substrings - Video Solutions

Problem Overview: You receive a string s. For every substring, compute its beauty, defined as the difference between the highest character frequency and the lowest non‑zero frequency in that substring. The goal is to sum this beauty value across all possible substrings.

Approach 1: Brute Force Frequency Recalculation (O(n^3) time, O(1) space)

The most direct method enumerates every substring using two indices i and j. For each substring s[i..j], rebuild a frequency array for the 26 lowercase characters, then compute the maximum and minimum non‑zero counts. The beauty value (maxFreq - minFreq) is added to the total. Because you recompute character counts for each substring, the inner operation scans the substring again, producing roughly O(n^3) time. Space stays O(1) since the alphabet size is constant. This approach is simple but inefficient for larger strings.

Approach 2: Optimized Expansion with Running Frequency (O(n^2) time, O(1) space)

A better approach fixes the starting index i and expands the substring one character at a time. Maintain a frequency array of size 26 while extending j. Each step updates the count of s[j], then recomputes the current maximum and minimum non‑zero frequencies by scanning the 26-element array. Since the alphabet is fixed, this scan is constant time. The substring frequencies are reused instead of rebuilt, reducing complexity to O(n^2). This technique relies on efficient character counting using a small array or hash table, combined with incremental substring growth from the string.

Approach 3: Prefix Frequency Precomputation (O(n^2) time, O(26n) space)

You can also build prefix frequency arrays where prefix[i][c] stores how many times character c appears up to index i. For any substring s[l..r], compute each character’s frequency using prefix[r] - prefix[l-1]. After retrieving counts, determine the max and min non‑zero frequencies to calculate the beauty. This avoids maintaining a mutable array while iterating but still requires scanning all 26 characters per substring. The complexity remains O(n^2), with extra memory for prefix storage. It’s a clean approach when working heavily with counting queries across ranges.

Recommended for interviews: The incremental frequency expansion approach is the expected solution. It demonstrates understanding of substring enumeration while avoiding redundant recomputation. Interviewers usually accept O(n^2) because the alphabet is fixed and scanning 26 characters is effectively constant time. Showing the brute force method first proves you understand the definition of beauty, then optimizing with running counts shows practical problem‑solving skill.