1781. Sum of Beauty of All Substrings

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.

 

Solutions

Solution: counting

• Time complexity: O(n²)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const beautySum = function (s) {
  const CODE_BASE = 'a'.charCodeAt(0);
  const size = s.length;
  const frequencies = Array.from({length: 26}).fill(0);
  let result = 0;

  for (let a = 0; a < size - 1; a++) {
    frequencies[s.charCodeAt(a) - CODE_BASE] += 1;

    for (let b = a + 1; b < size; b++) {
      let maxCount = 0;
      let minCount = Number.MAX_SAFE_INTEGER;

      frequencies[s.charCodeAt(b) - CODE_BASE] += 1;
      frequencies
        .filter(count => count !== 0)
        .forEach(count => {
          maxCount = Math.max(count, maxCount);
          minCount = Math.min(count, minCount);
        });
      result += maxCount - minCount;
    }
    frequencies.fill(0);
  }
  return result;
};