Easy
题目描述
给你一个由小写英文字母组成的字符串 s。
对于值 k，频率组是在 s 中恰好出现 k 次的字符集合。
多数频率组是包含最多不同字符的频率组。
返回一个包含多数频率组中所有字符的字符串，字符顺序任意。如果两个或更多频率组的大小相同，选择频率 k 更大的组。
示例 1：
输入：s = "aaabbbccdddde"
输出："ab"
解释：
频率 (k) | 组中不同字符 | 组大小 | 是否为多数？
4 | {d} | 1 | 否
3 | {a, b} | 2 | 是
2 | {c} | 1 | 否
1 | {e} | 1 | 否
字符 'a' 和 'b' 都有频率 3，它们在多数频率组中。"ba" 也是有效答案。
示例 2：
输入：s = "abcd"
输出："abcd"
解释：
频率 (k) | 组中不同字符 | 组大小 | 是否为多数？
1 | {a, b, c, d} | 4 | 是
所有字符都有频率 1，它们都在多数频率组中。
示例 3：
输入：s = "pfpfgi"
输出："fp"
解释：
频率 (k) | 组中不同字符 | 组大小 | 是否为多数？
2 | {p, f} | 2 | 是
1 | {g, i} | 2 | 否（大小相同，频率更低）
字符 'p' 和 'f' 都有频率 2，它们在多数频率组中。频率 1 的组大小相同，但我们选择更高的频率：2。
约束条件：
1 <= s.length <= 100s只包含小写英文字母
提示：
- 首先统计字符串中每个字符的频率
- 根据频率对字符进行分组
- 找出包含最多不同字符的组
- 如果多个组大小相同，选择频率值更高的组
- 使用选中组的所有字符构造答案字符串
解题思路
这道题的核心思路是找到包含字符数量最多的频率组，如果存在平局则选择频率值更大的组。
算法步骤：
- 统计频率：遍历字符串，统计每个字符的出现次数
- 按频率分组：将具有相同频率的字符归为一组
- 找多数组：找到包含字符数量最多的频率组
- 处理平局：如果多个组字符数量相同，选择频率值更大的组
- 构造结果：将选中组的所有字符拼接成结果字符串
实现要点：
- 使用哈希表统计字符频率
- 使用另一个哈希表按频率分组字符
- 遍历所有频率组，找到最优的组（优先比较组大小，其次比较频率值）
- 最后将选中组的字符拼接返回
时间复杂度主要在于字符串遍历和分组操作，空间复杂度取决于不同字符和不同频率的数量。
代码实现
class Solution {
public:
string majorityFrequencyGroup(string s) {
// 统计每个字符的频率
unordered_map<char, int> charCount;
for (char c : s) {
charCount[c]++;
}
// 按频率分组字符
unordered_map<int, vector<char>> freqGroups;
for (auto& pair : charCount) {
freqGroups[pair.second].push_back(pair.first);
}
// 找到多数频率组
int maxSize = 0;
int bestFreq = 0;
for (auto& group : freqGroups) {
int freq = group.first;
int size = group.second.size();
if (size > maxSize || (size == maxSize && freq > bestFreq)) {
maxSize = size;
bestFreq = freq;
}
}
// 构造结果字符串
string result;
for (char c : freqGroups[bestFreq]) {
result += c;
}
return result;
}
};
class Solution:
def majorityFrequencyGroup(self, s: str) -> str:
# 统计每个字符的频率
char_count = {}
for c in s:
char_count[c] = char_count.get(c, 0) + 1
# 按频率分组字符
freq_groups = {}
for char, freq in char_count.items():
if freq not in freq_groups:
freq_groups[freq] = []
freq_groups[freq].append(char)
# 找到多数频率组
max_size = 0
best_freq = 0
for freq, chars in freq_groups.items():
size = len(chars)
if size > max_size or (size == max_size and freq > best_freq):
max_size = size
best_freq = freq
# 构造结果字符串
return ''.join(freq_groups[best_freq])
public class Solution {
public string MajorityFrequencyGroup(string s) {
// 统计每个字符的频率
var charCount = new Dictionary<char, int>();
foreach (char c in s) {
charCount[c] = charCount.GetValueOrDefault(c, 0) + 1;
}
// 按频率分组字符
var freqGroups = new Dictionary<int, List<char>>();
foreach (var pair in charCount) {
if (!freqGroups.ContainsKey(pair.Value)) {
freqGroups[pair.Value] = new List<char>();
}
freqGroups[pair.Value].Add(pair.Key);
}
// 找到多数频率组
int maxSize = 0;
int bestFreq = 0;
foreach (var group in freqGroups) {
int freq = group.Key;
int size = group.Value.Count;
if (size > maxSize || (size == maxSize && freq > bestFreq)) {
maxSize = size;
bestFreq = freq;
}
}
// 构造结果字符串
return string.Join("", freqGroups[bestFreq]);
}
}
var majorityFrequencyGroup = function(s) {
const charCount = {};
for (let char of s) {
charCount[char] = (charCount[char] || 0) + 1;
}
const freqGroups = {};
for (let char in charCount) {
const freq = charCount[char];
if (!freqGroups[freq]) {
freqGroups[freq] = [];
}
freqGroups[freq].push(char);
}
let maxGroupSize = 0;
let maxFreq = 0;
for (let freq in freqGroups) {
const groupSize = freqGroups[freq].length;
const freqNum = parseInt(freq);
if (groupSize > maxGroupSize || (groupSize === maxGroupSize && freqNum > maxFreq)) {
maxGroupSize = groupSize;
maxFreq = freqNum;
}
}
return freqGroups[maxFreq].join('');
};
复杂度分析
| 复杂度类型 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 时间复杂度 | O(n) | - |
| 空间复杂度 | - | O(k) |
其中 n 是字符串长度，k 是不同字符的数量（最多26个小写字母）。时间复杂度为 O(n)，因为需要遍历字符串统计频率，然后遍历字符和频率组。空间复杂度为 O(k)，用于存储字符频率和频率分组。