PPractick

The problem

A text-analysis contest defines the beauty of a string as the difference between the frequencies of its most common and least common characters (counting only characters that appear): "aabcb" has frequencies a:2, b:2, c:1, so its beauty is 1. The task is the total beauty over every substring. There are O(n²) substrings, and recounting each one from scratch is O(n³). Fixing the start and extending the end one character at a time lets the frequency table update in O(1), with a quick scan of 26 counters for the max and min.

Example: "aabcb" → 5.

Function signature

long long beautySum(const string& s);  // lowercase letters

Test cases

Input s	Output	Explanation
"aabcb"	5	"aab", "aabc", "aabcb", "abcb", "bcb" each have beauty 1
"aabcbaa"	17
"a"	0	A single character has beauty 0
"abc"	0	Every substring has all frequencies equal
"aab"	1	Only "aab" (2 − 1)

(Confirm: the minimum is taken over characters that appear in the substring; lowercase letters only.)

How interviewers phrase it

• "Sum of beauty of all substrings" (LeetCode 1781).
• A test of incremental computation: reuse work when extending a substring instead of recounting.

Clarifying questions to ask

1. Does the minimum ignore characters that don't appear? (Yes.)
2. What's the character set? (Lowercase letters here.)
3. How long can the string be? (O(26·n²) works for n up to about 500.)

Follow-ups to expect

1. "Why not recount each substring?"
2. "How do you get max and min quickly?"
3. "Could you avoid the 26-scan?"
4. "Complexity?"

Related questions

• Roman to Integer Medium
• Isomorphic String Easy
• Check if two strings are anagram of each other Easy
• Sort Characters by Frequency Easy
• Longest Repeating Character Replacement Hard
• Longest Substring With At Most K Distinct Characters Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in