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 仅由小写英文字母组成。

提示：

  • 维护字符频次的前缀和。
  • 可以遍历所有子字符串，然后遍历字母表，使用前缀和数组找到出现最多和最少的字符。

解题思路

解题思路

这道题要求计算所有子字符串的美丽值之和。美丽值定义为子字符串中最高频字符和最低频字符的频次差。

方法一：暴力枚举 + 频次统计（推荐）

最直观的思路是枚举所有子字符串，对每个子字符串计算其美丽值：

  1. 外层循环确定子字符串的起始位置 i
  2. 内层循环确定子字符串的结束位置 j，同时维护当前子字符串的字符频次
  3. 对于每个子字符串 s[i:j+1]，遍历26个字母找出最大频次和最小频次（频次大于0）
  4. 累加所有子字符串的美丽值

方法二：前缀和优化

题目提示中提到了前缀和，但考虑到字符串长度限制（≤500），暴力方法已经足够高效。前缀和优化主要是预计算每个位置的字符频次，然后通过差值快速获得任意子字符串的频次分布。

由于约束条件较小，推荐使用方法一，代码更简洁易懂。时间复杂度为 O(n² × 26)，完全可以接受。

代码实现

class Solution {
public:
    int beautySum(string s) {
        int n = s.length();
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            vector<int> freq(26, 0);
            for (int j = i; j < n; j++) {
                freq[s[j] - 'a']++;
                
                int maxFreq = 0, minFreq = INT_MAX;
                for (int k = 0; k < 26; k++) {
                    if (freq[k] > 0) {
                        maxFreq = max(maxFreq, freq[k]);
                        minFreq = min(minFreq, freq[k]);
                    }
                }
                
                result += maxFreq - minFreq;
            }
        }
        
        return result;
    }
};

class Solution:
    def beautySum(self, s: str) -> int:
        n = len(s)
        result = 0
        
        for i in range(n):
            freq = [0] * 26
            for j in range(i, n):
                freq[ord(s[j]) - ord('a')] += 1
                
                non_zero_freqs = [f for f in freq if f > 0]
                if non_zero_freqs:
                    result += max(non_zero_freqs) - min(non_zero_freqs)
        
        return result

public class Solution {
    public int BeautySum(string s) {
        int n = s.Length;
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            for (int j = i; j < n; j++) {
                freq[s[j] - 'a']++;
                
                int maxFreq = 0, minFreq = int.MaxValue;
                for (int k = 0; k < 26; k++) {
                    if (freq[k] > 0) {
                        maxFreq = Math.Max(maxFreq, freq[k]);
                        minFreq = Math.Min(minFreq, freq[k]);
                    }
                }
                
                result += maxFreq - minFreq;
            }
        }
        
        return result;
    }
}

var beautySum = function(s) {
    const n = s.length;
    let result = 0;
    
    for (let i = 0; i < n; i++) {
        const freq = new Array(26).fill(0);
        for (let j = i; j < n; j++) {
            freq[s.charCodeAt(j) - 97]++;
            
            let maxFreq = 0, minFreq = Infinity;
            for (let k = 0; k < 26; k++) {
                if (freq[k] > 0) {
                    maxFreq = Math.max(maxFreq, freq[k]);
                    minFreq = Math.min(minFreq, freq[k]);
                }
            }
            
            result += maxFreq - minFreq;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n² × 26) = O(n²)
空间复杂度O(26) = O(1)

其中 n 是字符串的长度。外层循环 O(n)，内层循环 O(n)，每次需要遍历26个字母统计频次，总体时间复杂度为 O(n²)。空间复杂度为常数级别，只需要存储26个字母的频次数组。

相关题目