class Solution {
public:
bool equalFrequency(string word) {
}
};
2423. 删除字符使频率相同
给你一个下标从 0 开始的字符串 word ，字符串只包含小写英文字母。你需要选择 一个 下标并 删除 下标处的字符，使得 word 中剩余每个字母出现 频率 相同。
如果删除一个字母后，word 中剩余所有字母的出现频率都相同，那么返回 true ，否则返回 false 。
注意：
x 的 频率 是这个字母在字符串中出现的次数。
示例 1：
输入：word = "abcc" 输出：true 解释：选择下标 3 并删除该字母，word 变成 "abc" 且每个字母出现频率都为 1 。
示例 2：
输入：word = "aazz" 输出：false 解释：我们必须删除一个字母，所以要么 "a" 的频率变为 1 且 "z" 的频率为 2 ，要么两个字母频率反过来。所以不可能让剩余所有字母出现频率相同。
提示：
2 <= word.length <= 100word 只包含小写英文字母。原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-27 14:31:17
func equalFrequency(word string) bool {
mCnt := map[rune]int{}
for _, c := range word {
mCnt[c]++
}
cnt := make([]int, 0, len(mCnt))
for _, c := range mCnt {
cnt = append(cnt, c)
}
sort.Ints(cnt) // 出现次数从小到大排序
m := len(cnt)
// 只有一种字符 or 去掉次数最少的 or 去掉次数最多的
return m == 1 ||
cnt[0] == 1 && isSame(cnt[1:]) ||
cnt[m-1] == cnt[m-2]+1 && isSame(cnt[:m-1])
}
func isSame(a []int) bool {
for _, x := range a[1:] {
if x != a[0] {
return false
}
}
return true
}
// 暴力枚举
func equalFrequency2(word string) bool {
next:
for i := range word { // 枚举删除的字符
cnt := map[rune]int{}
for j, c := range word {
if j != i {
cnt[c]++ // 统计出现次数
}
}
c0 := 0
for _, c := range cnt {
if c0 == 0 {
c0 = c
} else if c != c0 { // 出现次数不一样
continue next // 枚举下一个字符
}
}
return true // 循环没有中途退出，说明出现次数都一样
}
return false
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.4 MB, 提交时间: 2023-09-27 14:30:27
class Solution {
bool is_same(unordered_map<char, int> &cnt) {
int c0 = cnt.begin()->second;
for (auto &[_, c]: cnt)
if (c != c0)
return false;
return true;
}
public:
bool equalFrequency1(string word) {
int n = word.length();
for (int i = 0; i < n; ++i) { // 枚举删除的字符
unordered_map<char, int> cnt;
for (int j = 0; j < n; ++j)
if (j != i)
++cnt[word[j]]; // 统计出现次数
if (is_same(cnt)) // 出现次数都一样
return true;
}
return false;
}
// 分类讨论
bool equalFrequency(string word) {
unordered_map<char, int> m_cnt;
for (char c: word)
++m_cnt[c];
vector<int> cnt;
for (auto &[_, c]: m_cnt)
cnt.push_back(c);
sort(cnt.begin(), cnt.end()); // 出现次数从小到大排序
// 只有一种字符 or 去掉次数最少的 or 去掉次数最多的
return cnt.size() == 1 ||
cnt[0] == 1 && equal(cnt.begin() + 2, cnt.end(), cnt.begin() + 1) ||
cnt.back() == cnt[cnt.size() - 2] + 1 && equal(cnt.begin() + 1, cnt.end() - 1, cnt.begin());
}
};
java 解法, 执行用时: 2 ms, 内存消耗: 39.6 MB, 提交时间: 2023-09-27 14:29:45
class Solution {
// 分类讨论
public boolean equalFrequency(String word) {
var mCnt = new HashMap<Character, Integer>();
for (var c : word.toCharArray())
mCnt.merge(c, 1, Integer::sum);
var cnt = new ArrayList<>(mCnt.values());
Collections.sort(cnt); // 出现次数从小到大排序
int m = cnt.size();
// 只有一种字符 or 去掉次数最少的 or 去掉次数最多的
return m == 1 ||
cnt.get(0) == 1 && isSame(cnt.subList(1, m)) ||
cnt.get(m - 1) == cnt.get(m - 2) + 1 && isSame(cnt.subList(0, m - 1));
}
private boolean isSame(List<Integer> cnt) {
int c0 = cnt.get(0);
for (int c : cnt)
if (c != c0)
return false;
return true;
}
// 暴力枚举
public boolean equalFrequency2(String word) {
var s = word.toCharArray();
int n = s.length;
for (int i = 0; i < n; ++i) { // 枚举删除的字符
var cnt = new HashMap<Character, Integer>();
for (int j = 0; j < n; ++j)
if (j != i)
cnt.merge(s[j], 1, Integer::sum); // 统计出现次数
if (isSame2(cnt)) // 出现次数都一样
return true;
}
return false;
}
private boolean isSame2(Map<Character, Integer> cnt) {
int c0 = cnt.entrySet().iterator().next().getValue();
for (int c : cnt.values())
if (c != c0)
return false;
return true;
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 16 MB, 提交时间: 2023-09-27 14:28:28
class Solution:
# 暴力枚举
def equalFrequency(self, word: str) -> bool:
for i in range(len(word)): # 枚举删除的字符
cnt = Counter(word[:i] + word[i + 1:]) # 统计出现次数
if len(set(cnt.values())) == 1: # 出现次数都一样
return True
return False
python3 解法, 执行用时: 32 ms, 内存消耗: 14.9 MB, 提交时间: 2022-10-09 11:04:22
class Solution:
def equalFrequency(self, word: str) -> bool:
for i in range(len(word)):
cnt = Counter(word[:i] + word[i + 1:])
same = cnt.popitem()[1]
if all(c == same for c in cnt.values()):
return True
return False
python3 解法, 执行用时: 32 ms, 内存消耗: 14.9 MB, 提交时间: 2022-10-09 11:03:19
class Solution:
def equalFrequency(self, word: str) -> bool:
c = sorted(Counter(word).values())
return len(c) == 1 or c[0] == 1 and len(set(c[1:])) == 1 or c[-1] == c[-2] + 1 and len(set(c[:-1])) == 1