给你一个下标从 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 <= 100
word
只包含小写英文字母。
方法一:直接模拟
遍历字符串中的每个字符,删除该字符后,判断剩余字符串中每个字符出现的频率是否相同。如果相同,返回 true
,否则遍历结束,返回 false
。
时间复杂度
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
class Solution {
public boolean equalFrequency(String word) {
for (int i = 0; i < word.length(); ++i) {
int[] cnt = new int[26];
for (int j = 0; j < word.length(); ++j) {
if (j != i) {
++cnt[word.charAt(j) - 'a'];
}
}
Set<Integer> vis = new HashSet<>();
for (int v : cnt) {
if (v > 0) {
vis.add(v);
}
}
if (vis.size() == 1) {
return true;
}
}
return false;
}
}
class Solution {
public:
bool equalFrequency(string word) {
for (int i = 0; i < word.size(); ++i) {
int cnt[26] = {0};
for (int j = 0; j < word.size(); ++j) {
if (j != i) {
++cnt[word[j] - 'a'];
}
}
unordered_set<int> vis;
for (int v : cnt) {
if (v) {
vis.insert(v);
}
}
if (vis.size() == 1) {
return true;
}
}
return false;
}
};
func equalFrequency(word string) bool {
for i := range word {
cnt := make([]int, 26)
for j, c := range word {
if j != i {
cnt[c-'a']++
}
}
vis := map[int]bool{}
for _, v := range cnt {
if v > 0 {
vis[v] = true
}
}
if len(vis) == 1 {
return true
}
}
return false
}
function equalFrequency(word: string): boolean {
const map = new Map();
for (const c of word) {
map.set(c, (map.get(c) ?? 0) + 1);
}
const count = new Map();
for (const v of map.values()) {
count.set(v, (count.get(v) ?? 0) + 1);
}
if (count.size === 1) {
return map.size == 1 || [...count.keys()][0] === 1;
}
if (count.size === 2) {
return [...count.entries()].some(
(v, i, arr) =>
(v[0] === 1 || v[0] - arr[i ^ 1][0] === 1) && v[1] === 1,
);
}
return false;
}