【2022-12-12每日一题】1781. 所有子字符串美丽值之和[Medium]

2022-12-12每日一题：1781. 所有子字符串美丽值之和

难度：Medium

标签：哈希表 、 字符串 、 计数

一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。

• 比方说，"abaacc" 的美丽值为 3 - 1 = 2 。

给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。

示例 1：

输入：s = "aabcb"
输出：5
解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。

示例 2：

输入：s = "aabcbaa"
输出：17

提示：

• 1 <= s.length <= 500
• s 只包含小写英文字母。

方法一：暴力枚举+计数

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

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

• 时间复杂度：$O(C×n^2)$，其中 C 是 s 的元素种类，n 是 s 的长度。

• 空间复杂度：O(C)。

LeetCode题库地址

• https://leetcode.cn/problems/sum-of-beauty-of-all-substrings