Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.
"abaacc" is 3 - 1 = 2.Given a string s, return the sum of beauty of all of its substrings.
Example 1:
Input: s = "aabcb" Output: 5 Explanation: The substrings with non-zero beauty are ["aab","aabc","aabcb","abcb","bcb"], each with beauty equal to 1.
Example 2:
Input: s = "aabcbaa" Output: 17
Constraints:
1 <= s.length <= 500s consists of only lowercase English letters.Problem summary: The beauty of a string is the difference in frequencies between the most frequent and least frequent characters. For example, the beauty of "abaacc" is 3 - 1 = 2. Given a string s, return the sum of beauty of all of its substrings.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map
"aabcb"
"aabcbaa"
substrings-that-begin-and-end-with-the-same-letter)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1781: Sum of Beauty of All Substrings
class Solution {
public int beautySum(String s) {
int ans = 0;
int n = s.length();
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 mi = 1000, mx = 0;
for (int v : cnt) {
if (v > 0) {
mi = Math.min(mi, v);
mx = Math.max(mx, v);
}
}
ans += mx - mi;
}
}
return ans;
}
}
// Accepted solution for LeetCode #1781: Sum of Beauty of All Substrings
func beautySum(s string) (ans int) {
for i := range s {
cnt := [26]int{}
for j := i; j < len(s); j++ {
cnt[s[j]-'a']++
mi, mx := 1000, 0
for _, v := range cnt {
if v > 0 {
if mi > v {
mi = v
}
if mx < v {
mx = v
}
}
}
ans += mx - mi
}
}
return
}
# Accepted solution for LeetCode #1781: Sum of Beauty of All Substrings
class Solution:
def beautySum(self, s: str) -> int:
ans, n = 0, len(s)
for i in range(n):
cnt = Counter()
for j in range(i, n):
cnt[s[j]] += 1
ans += max(cnt.values()) - min(cnt.values())
return ans
// Accepted solution for LeetCode #1781: Sum of Beauty of All Substrings
impl Solution {
pub fn beauty_sum(s: String) -> i32 {
let mut ans = 0;
let n = s.len();
let s: Vec<char> = s.chars().collect();
for i in 0..n {
let mut cnt = vec![0; 26];
for j in i..n {
cnt[s[j] as usize - 'a' as usize] += 1;
let mut mi = 1000;
let mut mx = 0;
for &v in &cnt {
if v > 0 {
mi = mi.min(v);
mx = mx.max(v);
}
}
ans += mx - mi;
}
}
ans
}
}
// Accepted solution for LeetCode #1781: Sum of Beauty of All Substrings
function beautySum(s: string): number {
let ans = 0;
for (let i = 0; i < s.length; ++i) {
const cnt = new Map();
for (let j = i; j < s.length; ++j) {
cnt.set(s[j], (cnt.get(s[j]) || 0) + 1);
const t = Array.from(cnt.values());
ans += Math.max(...t) - Math.min(...t);
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.