Easy

题目描述

给你一个由小写英文字母（‘a’ 到 ‘z’）组成的字符串 s。

你的任务是：

  • 找到频率最高的元音字母（‘a’、’e’、‘i’、‘o’ 或 ‘u’ 中的一个）
  • 找到频率最高的辅音字母（除元音字母外的所有其他字母）

返回这两个频率的和。

注意： 如果多个元音或辅音具有相同的最大频率，你可以选择其中任何一个。如果字符串中没有元音或没有辅音，则将其频率视为 0。 字母 x 的频率是它在字符串中出现的次数。

示例 1：

输入：s = "successes"
输出：6
解释：
- 元音字母有：'u'（频率 1）、'e'（频率 2）。最大频率是 2。
- 辅音字母有：'s'（频率 4）、'c'（频率 2）。最大频率是 4。
- 输出是 2 + 4 = 6。

示例 2：

输入：s = "aeiaeia"
输出：3
解释：
- 元音字母有：'a'（频率 3）、'e'（频率 2）、'i'（频率 2）。最大频率是 3。
- 字符串中没有辅音字母，因此最大辅音频率 = 0。
- 输出是 3 + 0 = 3。

约束条件：

  • 1 <= s.length <= 100
  • s 仅由小写英文字母组成

解题思路

这道题的解题思路非常直观，可以分为以下几个步骤：

核心思路：

  1. 使用哈希表分别统计元音和辅音字母的频率
  2. 遍历字符串，将每个字符按元音/辅音分类并统计频率
  3. 找出元音字母中的最大频率和辅音字母中的最大频率
  4. 返回两个最大频率的和

具体实现：

  • 首先定义元音字母集合 {'a', 'e', 'i', 'o', 'u'}
  • 使用两个哈希表分别存储元音和辅音的频率统计
  • 遍历字符串中的每个字符，判断是元音还是辅音，并更新对应的频率计数
  • 分别在元音和辅音的频率表中找到最大值
  • 如果某类字母不存在（哈希表为空），则该类的最大频率为 0

时间复杂度分析：

  • 遍历字符串需要 O(n) 时间
  • 查找最大频率需要 O(k) 时间，其中 k 是不同字符的数量，最多为 26
  • 总体时间复杂度为 O(n)

空间复杂度分析：

  • 需要两个哈希表存储频率，最坏情况下存储所有 26 个字母
  • 空间复杂度为 O(1)，因为字母数量是常数

代码实现

class Solution {
public:
    int maxFreqSum(string s) {
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
        unordered_map<char, int> vowelCount, consonantCount;
        
        for (char c : s) {
            if (vowels.count(c)) {
                vowelCount[c]++;
            } else {
                consonantCount[c]++;
            }
        }
        
        int maxVowelFreq = 0, maxConsonantFreq = 0;
        
        for (auto& p : vowelCount) {
            maxVowelFreq = max(maxVowelFreq, p.second);
        }
        
        for (auto& p : consonantCount) {
            maxConsonantFreq = max(maxConsonantFreq, p.second);
        }
        
        return maxVowelFreq + maxConsonantFreq;
    }
};

class Solution:
    def maxFreqSum(self, s: str) -> int:
        vowels = set('aeiou')
        vowel_count = {}
        consonant_count = {}
        
        for c in s:
            if c in vowels:
                vowel_count[c] = vowel_count.get(c, 0) + 1
            else:
                consonant_count[c] = consonant_count.get(c, 0) + 1
        
        max_vowel_freq = max(vowel_count.values()) if vowel_count else 0
        max_consonant_freq = max(consonant_count.values()) if consonant_count else 0
        
        return max_vowel_freq + max_consonant_freq

public class Solution {
    public int MaxFreqSum(string s) {
        HashSet<char> vowels = new HashSet<char>{'a', 'e', 'i', 'o', 'u'};
        Dictionary<char, int> vowelCount = new Dictionary<char, int>();
        Dictionary<char, int> consonantCount = new Dictionary<char, int>();
        
        foreach (char c in s) {
            if (vowels.Contains(c)) {
                vowelCount[c] = vowelCount.GetValueOrDefault(c, 0) + 1;
            } else {
                consonantCount[c] = consonantCount.GetValueOrDefault(c, 0) + 1;
            }
        }
        
        int maxVowelFreq = vowelCount.Count > 0 ? vowelCount.Values.Max() : 0;
        int maxConsonantFreq = consonantCount.Count > 0 ? consonantCount.Values.Max() : 0;
        
        return maxVowelFreq + maxConsonantFreq;
    }
}

var maxFreqSum = function(s) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    const vowelCount = new Map();
    const consonantCount = new Map();
    
    for (const c of s) {
        if (vowels.has(c)) {
            vowelCount.set(c, (vowelCount.get(c) || 0) + 1);
        } else {
            consonantCount.set(c, (consonantCount.get(c) || 0) + 1);
        }
    }
    
    const maxVowelFreq = vowelCount.size > 0 ? Math.max(...vowelCount.values()) : 0;
    const maxConsonantFreq = consonantCount.size > 0 ? Math.max(...consonantCount.values()) : 0;
    
    return maxVowelFreq + maxConsonantFreq;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，其中 n 是字符串长度
空间复杂度O(1)哈希表最多存储 26 个字母，为常数空间