Krammer's blog

https://leetcode.com/problems/sum-of-beauty-of-all-substrings/ from Google

Thinking process:

For this problem, since the length of the string is at most 500, we can afford a N^2 solution. With this, we iterate through the string with two pointers, and then count the frequency of each letter. In each round, we can check the whole 26 letters to find the most frequent and least frequent characters and then count the beauty.

Here is the code.

 1class Solution {
 2public:
 3    int beautySum(string s) {
 4        int N = s.size();
 5        int ans = 0;
 6        for (int i=0; i<N; i++) {
 7            vector<int> cnt(26);
 8            for (int j=i; j<N; j++) {
 9                cnt[s[j]-'a']++;
10                int M = 0, m = N;
11                for (int k=0; k<26; k++) {
12                    if (cnt[k] == 0) continue;
13                    M = max(M, cnt[k]);
14                    m = min(m, cnt[k]);
15                }
16                ans += (M - m);
17            }
18        }
19        return ans;
20    }
21};

Editorial: LeetCode 1781 Sum of Beauty of All Substrings