Formatted question description: https://leetcode.ca/all/1781.html

1781. Sum of Beauty of All Substrings

Level

Medium

Description

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.

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.

Solution

Loop over i from 0 to s.length() - 1. For each i, maintain a tree map and loop over j from i to s.length() - 1. For s.substring(i, j + 1), store the frequencies of each character, and store the frequencies in the tree map. Use the tree map’s last key and first key to get the maximum frequency and the minimum frequency, and to calculate the beauty of the substring. Finally, return the sum of beauty of all the substrings of s.

  • class Solution {
        public int beautySum(String s) {
            int sum = 0;
            int length = s.length();
            for (int i = 0; i < length; i++) {
                int[] counts = new int[26];
                TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
                for (int j = i; j < length; j++) {
                    char c = s.charAt(j);
                    int index = c - 'a';
                    counts[index]++;
                    int count = counts[index];
                    map.put(count, map.getOrDefault(count, 0) + 1);
                    if (map.containsKey(count - 1)) {
                        map.put(count - 1, map.get(count - 1) - 1);
                        if (map.get(count - 1) == 0)
                            map.remove(count - 1);
                    }
                    int maxFreq = map.lastKey();
                    int minFreq = map.firstKey();
                    sum += maxFreq - minFreq;
                }
            }
            return sum;
        }
    }
    
  • // OJ: https://leetcode.com/problems/sum-of-beauty-of-all-substrings/
    // Time: O(N^2)
    // Space: O(1)
    class Solution {
    public:
        int beautySum(string s) {
            int ans = 0;
            for (int i = 0; i < s.size(); ++i) {
                int cnt[26] = {};
                for (int j = i; j < s.size(); ++j) {
                    ++cnt[s[j] - 'a'];
                    int mx = INT_MIN, mn = INT_MAX;
                    for (int k = 0; k < 26; ++k) {
                        mx = max(mx, cnt[k]);
                        if (cnt[k]) mn = min(mn, cnt[k]);
                    }
                    ans += mx - mn;
                }
            }
            return ans;
        }
    };
    
  • # 1781. Sum of Beauty of All Substrings
    # https://leetcode.com/problems/sum-of-beauty-of-all-substrings
    
    class Solution:
        def beautySum(self, s: str) -> int:
            n = len(s)
            res = 0
            
            for i in range(n):
                mp = collections.defaultdict(int)
                for j in range(i, n):
                    mp[s[j]] += 1
                    v = mp.values()
                    res += max(v) - min(v)
            
            return res
    
    

All Problems

All Solutions