Problem Statement:
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.
Examples:
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 <= 500
s consists of only lowercase English letters..
There is at least one word in s.
Time Complexity:
Time Complexity = O(n2)
Space Complexity:
Space Complexity = O(1)
Approach
-
Iterateover all possible substrings using two loops → Use an outer loop to fix the starting index and an inner loop to expand the substring one character at a time. -
Initialize a frequency array →
For each starting index, create a frequency array of size
26(for lowercase English letters) initialized with0. - Expand the substring → As the inner loop progresses, include one character at a time in the substring and update its frequency in the array.
-
For every substring:
- Update frequency → Increment the count of the current character in the frequency array.
-
Find maximum and minimum frequency →
Traverse the frequency array to determine:
max→ highest frequency of any character.min→ lowest frequency excluding0(ignore characters not present in the substring).
-
Calculate beauty → Add
(max - min)to the result for the current substring.
- Accumulate result → Keep adding the beauty value of each substring to a running total.
- Return the final sum → After processing all substrings, return the accumulated result.
Dry Run
Input: s = "aab"
Initial:
beautySum = 0
Outer Loop i = 0:
freq = [0...0] (size 26)
j = 0 → substring = "a"
freq['a'] = 1
max = 1, min = 1
beauty = max - min = 0
beautySum = 0
j = 1 → substring = "aa"
freq['a'] = 2
max = 2, min = 2
beauty = 0
beautySum = 0
j = 2 → substring = "aab"
freq['a'] = 2, freq['b'] = 1
max = 2, min = 1
beauty = 1
beautySum = 1
Outer Loop i = 1:
freq = [0...0]
j = 1 → substring = "a"
freq['a'] = 1
max = 1, min = 1
beauty = 0
beautySum = 1
j = 2 → substring = "ab"
freq['a'] = 1, freq['b'] = 1
max = 1, min = 1
beauty = 0
beautySum = 1
Outer Loop i = 2:
freq = [0...0]
j = 2 → substring = "b"
freq['b'] = 1
max = 1, min = 1
beauty = 0
beautySum = 1
Final:
beautySum = 1
Output: 1
var beautySum = function(s) {
let beautySum = 0;
for (let i = 0; i < s.length; i++) {
let freq = new Array(26).fill(0);
for (let j = i; j < s.length; j++) {
let index = s.charCodeAt(j) - "a".charCodeAt(0);
freq[index]++;
let max = 0;
let min = Infinity;
for (let k = 0; k < 26; k++) {
if (freq[k] > 0) {
max = Math.max(max, freq[k]);
min = Math.min(min, freq[k]);
}
}
beautySum += (max - min);
}
}
return beautySum;
};
def beautySum(s: str) -> int:
beauty_sum = 0
for i in range(len(s)):
freq = [0] * 26
for j in range(i, len(s)):
index = ord(s[j]) - ord('a')
freq[index] += 1
max_freq = 0
min_freq = float('inf')
for f in freq:
if f > 0:
max_freq = max(max_freq, f)
min_freq = min(min_freq, f)
beauty_sum += (max_freq - min_freq)
return beauty_sum
class Solution {
public int beautySum(String s) {
int beautySum = 0;
for (int i = 0; i < s.length(); i++) {
int[] freq = new int[26];
for (int j = i; j < s.length(); j++) {
int index = s.charAt(j) - 'a';
freq[index]++;
int max = 0;
int min = Integer.MAX_VALUE;
for (int k = 0; k < 26; k++) {
if (freq[k] > 0) {
max = Math.max(max, freq[k]);
min = Math.min(min, freq[k]);
}
}
beautySum += (max - min);
}
}
return beautySum;
}
}
class Solution {
public:
int beautySum(string s) {
int beautySum = 0;
for (int i = 0; i < s.length(); i++) {
vector freq(26, 0);
for (int j = i; j < s.length(); j++) {
int index = s[j] - 'a';
freq[index]++;
int maxFreq = 0;
int minFreq = INT_MAX;
for (int k = 0; k < 26; k++) {
if (freq[k] > 0) {
maxFreq = max(maxFreq, freq[k]);
minFreq = min(minFreq, freq[k]);
}
}
beautySum += (maxFreq - minFreq);
}
}
return beautySum;
}
};
#include <limits.h>
#include <string.h>
int beautySum(char* s) {
int beautySum = 0;
int n = strlen(s);
for (int i = 0; i < n; i++) {
int freq[26] = {0};
for (int j = i; j < n; j++) {
int index = s[j] - 'a';
freq[index]++;
int max = 0;
int min = INT_MAX;
for (int k = 0; k < 26; k++) {
if (freq[k] > 0) {
if (freq[k] > max) max = freq[k];
if (freq[k] < min) min = freq[k];
}
}
beautySum += (max - min);
}
}
return beautySum;
}
public class Solution {
public int BeautySum(string s) {
int beautySum = 0;
for (int i = 0; i < s.Length; i++) {
int[] freq = new int[26];
for (int j = i; j < s.Length; j++) {
int index = s[j] - 'a';
freq[index]++;
int max = 0;
int min = int.MaxValue;
for (int k = 0; k < 26; k++) {
if (freq[k] > 0) {
max = Math.Max(max, freq[k]);
min = Math.Min(min, freq[k]);
}
}
beautySum += (max - min);
}
}
return beautySum;
}
}
