LeetCode 2423: Remove Letter To Equalize Frequency (Try Removing One Character + Frequency Validation)
LeetCode 2423StringCountingFrequencyToday we solve LeetCode 2423 - Remove Letter To Equalize Frequency.
Source: https://leetcode.com/problems/remove-letter-to-equalize-frequency/
English
Problem Summary
Given a lowercase string word, remove exactly one character so that all remaining characters that appear have the same frequency. Return whether this is possible.
Key Insight
The alphabet size is only 26. We can try removing one occurrence from each letter that currently exists, then verify whether all non-zero frequencies become equal.
Algorithm
1) Count frequency of each letter.
2) For each letter with frequency > 0:
- temporarily decrease it by 1;
- scan all 26 counts and check whether non-zero counts are identical;
- restore the count.
3) If any trial passes, return true; otherwise return false.
Complexity Analysis
Time: O(26 * 26) (constant) after counting, equivalent to O(n) overall with counting.
Space: O(26).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean equalFrequency(String word) {
int[] cnt = new int[26];
for (char c : word.toCharArray()) cnt[c - 'a']++;
for (int i = 0; i < 26; i++) {
if (cnt[i] == 0) continue;
cnt[i]--;
if (allEqualNonZero(cnt)) return true;
cnt[i]++;
}
return false;
}
private boolean allEqualNonZero(int[] cnt) {
int target = 0;
for (int x : cnt) {
if (x == 0) continue;
if (target == 0) target = x;
else if (x != target) return false;
}
return true;
}
}func equalFrequency(word string) bool {
cnt := make([]int, 26)
for _, ch := range word {
cnt[ch-'a']++
}
for i := 0; i < 26; i++ {
if cnt[i] == 0 {
continue
}
cnt[i]--
if allEqualNonZero(cnt) {
return true
}
cnt[i]++
}
return false
}
func allEqualNonZero(cnt []int) bool {
target := 0
for _, x := range cnt {
if x == 0 {
continue
}
if target == 0 {
target = x
} else if x != target {
return false
}
}
return true
}class Solution {
public:
bool equalFrequency(string word) {
vector<int> cnt(26, 0);
for (char c : word) cnt[c - 'a']++;
for (int i = 0; i < 26; i++) {
if (cnt[i] == 0) continue;
cnt[i]--;
if (allEqualNonZero(cnt)) return true;
cnt[i]++;
}
return false;
}
bool allEqualNonZero(const vector<int>& cnt) {
int target = 0;
for (int x : cnt) {
if (x == 0) continue;
if (target == 0) target = x;
else if (x != target) return false;
}
return true;
}
};class Solution:
def equalFrequency(self, word: str) -> bool:
cnt = [0] * 26
for ch in word:
cnt[ord(ch) - ord('a')] += 1
def all_equal_non_zero(arr: list[int]) -> bool:
target = 0
for x in arr:
if x == 0:
continue
if target == 0:
target = x
elif x != target:
return False
return True
for i in range(26):
if cnt[i] == 0:
continue
cnt[i] -= 1
if all_equal_non_zero(cnt):
return True
cnt[i] += 1
return Falsevar equalFrequency = function(word) {
const cnt = new Array(26).fill(0);
for (const ch of word) cnt[ch.charCodeAt(0) - 97]++;
const allEqualNonZero = (arr) => {
let target = 0;
for (const x of arr) {
if (x === 0) continue;
if (target === 0) target = x;
else if (x !== target) return false;
}
return true;
};
for (let i = 0; i < 26; i++) {
if (cnt[i] === 0) continue;
cnt[i]--;
if (allEqualNonZero(cnt)) return true;
cnt[i]++;
}
return false;
};中文
题目概述
给定一个仅含小写字母的字符串 word，要求恰好删除一个字符，使剩余所有出现过的字符频次相同。判断是否可行。
核心思路
字母只有 26 个。我们可以枚举“删哪个字母的一次出现”，每次删完后检查所有非零频次是否一致。只要有一次成立就返回 true。
算法步骤
1）统计 26 个字母频次。
2）遍历每个频次 > 0 的字母：
- 临时减 1，模拟删除一个字符；
- 扫描 26 个频次，检查所有非零值是否相等；
- 恢复该字母频次。
3）任意一次检查通过则返回 true，否则返回 false。
复杂度分析
时间复杂度：计数为 O(n)，检查部分最多 26 * 26，总体仍可视为 O(n)。
空间复杂度：O(26)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean equalFrequency(String word) {
int[] cnt = new int[26];
for (char c : word.toCharArray()) cnt[c - 'a']++;
for (int i = 0; i < 26; i++) {
if (cnt[i] == 0) continue;
cnt[i]--;
if (allEqualNonZero(cnt)) return true;
cnt[i]++;
}
return false;
}
private boolean allEqualNonZero(int[] cnt) {
int target = 0;
for (int x : cnt) {
if (x == 0) continue;
if (target == 0) target = x;
else if (x != target) return false;
}
return true;
}
}func equalFrequency(word string) bool {
cnt := make([]int, 26)
for _, ch := range word {
cnt[ch-'a']++
}
for i := 0; i < 26; i++ {
if cnt[i] == 0 {
continue
}
cnt[i]--
if allEqualNonZero(cnt) {
return true
}
cnt[i]++
}
return false
}
func allEqualNonZero(cnt []int) bool {
target := 0
for _, x := range cnt {
if x == 0 {
continue
}
if target == 0 {
target = x
} else if x != target {
return false
}
}
return true
}class Solution {
public:
bool equalFrequency(string word) {
vector<int> cnt(26, 0);
for (char c : word) cnt[c - 'a']++;
for (int i = 0; i < 26; i++) {
if (cnt[i] == 0) continue;
cnt[i]--;
if (allEqualNonZero(cnt)) return true;
cnt[i]++;
}
return false;
}
bool allEqualNonZero(const vector<int>& cnt) {
int target = 0;
for (int x : cnt) {
if (x == 0) continue;
if (target == 0) target = x;
else if (x != target) return false;
}
return true;
}
};class Solution:
def equalFrequency(self, word: str) -> bool:
cnt = [0] * 26
for ch in word:
cnt[ord(ch) - ord('a')] += 1
def all_equal_non_zero(arr: list[int]) -> bool:
target = 0
for x in arr:
if x == 0:
continue
if target == 0:
target = x
elif x != target:
return False
return True
for i in range(26):
if cnt[i] == 0:
continue
cnt[i] -= 1
if all_equal_non_zero(cnt):
return True
cnt[i] += 1
return Falsevar equalFrequency = function(word) {
const cnt = new Array(26).fill(0);
for (const ch of word) cnt[ch.charCodeAt(0) - 97]++;
const allEqualNonZero = (arr) => {
let target = 0;
for (const x of arr) {
if (x === 0) continue;
if (target === 0) target = x;
else if (x !== target) return false;
}
return true;
};
for (let i = 0; i < 26; i++) {
if (cnt[i] === 0) continue;
cnt[i]--;
if (allEqualNonZero(cnt)) return true;
cnt[i]++;
}
return false;
};
Comments