Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go
• Javascript

• 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;
      }
  }
  
  ############
  
  class Solution {
      public int beautySum(String s) {
          int ans = 0;
          int n = s.length();
          for (int i = 0; i < n; ++i) {
              int[] cnt = new int[26];
              for (int j = i; j < n; ++j) {
                  ++cnt[s.charAt(j) - 'a'];
                  int mi = 1000, mx = 0;
                  for (int v : cnt) {
                      if (v > 0) {
                          mi = Math.min(mi, v);
                          mx = Math.max(mx, v);
                      }
                  }
                  ans += mx - mi;
              }
          }
          return ans;
      }
  }
  

• // 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;
      }
  };
  

• class Solution:
      def beautySum(self, s: str) -> int:
          ans, n = 0, len(s)
          for i in range(n):
              cnt = Counter()
              for j in range(i, n):
                  cnt[s[j]] += 1
                  ans += max(cnt.values()) - min(cnt.values())
          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
  
  

• func beautySum(s string) (ans int) {
  	for i := range s {
  		cnt := [26]int{}
  		for j := i; j < len(s); j++ {
  			cnt[s[j]-'a']++
  			mi, mx := 1000, 0
  			for _, v := range cnt {
  				if v > 0 {
  					if mi > v {
  						mi = v
  					}
  					if mx < v {
  						mx = v
  					}
  				}
  			}
  			ans += mx - mi
  		}
  	}
  	return
  }
  

• /**
   * @param {string} s
   * @return {number}
   */
  var beautySum = function (s) {
      let ans = 0;
      for (let i = 0; i < s.length; ++i) {
          const cnt = new Map();
          for (let j = i; j < s.length; ++j) {
              cnt.set(s[j], (cnt.get(s[j]) || 0) + 1);
              const t = Array.from(cnt.values());
              ans += Math.max(...t) - Math.min(...t);
          }
      }
      return ans;
  };
  
  

All Problems

All Solutions