Strings Counting over substrings
141. Sum of Beauty of All Substrings
You are given a string s of lowercase English letters. The beauty of a string is the number of times its
most common letter appears minus the number of times its least common letter appears. Letters that do not
appear are left out, so the beauty of abb is 2 − 1 = 1.
Return the sum of the beauty of every substring of s.
A substring is a block of letters that sit next to each other in s, with at least one letter. Two
substrings are different if they start or end at different positions, even when they hold the same letters.
Example 1
Input: s = "xyxxz"
8Explanation: xyxx and xyxxz have beauty 2, since x appears three times and y once. xyx, yxx, yxxz and
xxz have beauty 1, and every other substring has beauty 0, so the sum is 2 + 2 + 1 + 1 + 1 + 1 = 8.
Example 2
Input: s = "aab"
1Explanation: Only aab has a beauty above 0: a appears twice and b once. The letter b does not appear in aa,
so the beauty of aa is 2 − 2 = 0.
Example 3
Input: s = "zzzz"
0Explanation: Every substring holds only z, so its most common and least common letter are the same, and every beauty
is 0.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ s.length ≤ 1000sholds lowercase English letters only,atoz.
Clarifying questions
What you would ask an interviewer before writing any code.