Sum of Beauty of All Substrings
Problem Overview
The beauty of a substring is its highest letter count minus its lowest count among letters that actually appear.
Intuition
The beauty of a substring is its highest letter count minus its lowest count among letters that actually appear. There are n squared substrings, and each one is the previous substring plus one letter. That letter changes only one frequency. The new maximum is the larger of the old maximum and the new count. The minimum moves in two cases only. A letter that was absent now has count 1, so the minimum becomes 1. If that letter was the last one sitting at the old minimum, every other letter was already at least one higher, so the minimum rises by exactly 1. Every other addition leaves the minimum where it was.
Algorithm
- 1For each start index, clear a frequency array of 26 and a count of counts array whose index is a frequency.
- 2Extend the end one letter at a time. Move that letter from its old frequency bucket into the next bucket.
- 3Raise the maximum when the new frequency beats it.
- 4Set the minimum to 1 when the letter is new. Raise the minimum by 1 when its old bucket is now empty and that bucket was the minimum.
- 5Add maximum minus minimum to the answer.
Example Walkthrough
Input: s = "aabcb"
- 1. The substring "aa" uses only a, twice, so its beauty is 0.
- 2. Extending it to "aab" gives a count of 2 and b a count of 1. Beauty is 2 minus 1, which is 1.
- 3. The five substrings aab, aabc, aabcb, abcb, and bcb each contribute 1. Every other substring contributes 0.
Output: 5
Common Pitfalls
- • A letter with frequency 0 is absent. Counting it would pull every minimum down to 0 and make beauty equal the maximum.
- • When several letters share the minimum and one of them is incremented, the minimum stays. It rises only when the old minimum bucket becomes empty.
- • A brand new letter always has frequency 1, even when the current minimum is higher. The minimum drops back to 1.
- • A single letter, and any substring where every present letter has the same count, contributes 0.
// Approach: The beauty of a substring is its highest letter count minus its
// lowest positive letter count. Extending the substring by one letter changes
// only that letter's count. A count-of-counts array updates the maximum in
// one step. The minimum stays put unless the added letter was a new letter
// or the last letter sitting at the old minimum, in which case the minimum
// becomes 1 or rises by 1.
// Complexity: O(n^2) time, O(n) extra space.
class Solution {
public int beautySum(String s) {
int n = s.length();
int[] freq = new int[26];
int[] countAt = new int[n + 1];
int ans = 0;
for (int i = 0; i < n; i++) {
java.util.Arrays.fill(freq, 0);
java.util.Arrays.fill(countAt, 0);
int max = 0;
int min = 0;
for (int j = i; j < n; j++) {
int old = freq[s.charAt(j) - 'a']++;
if (old > 0)
countAt[old]--;
countAt[old + 1]++;
if (old + 1 > max)
max = old + 1;
if (old == 0)
min = 1;
else if (old == min && countAt[old] == 0)
min++;
ans += max - min;
}
}
return ans;
}
}