LeetCode 2423. 删除字符使频率相同

【LetMeFly】2423.删除字符使频率相同

力扣题目链接：https://leetcode.cn/problems/remove-letter-to-equalize-frequency/

给你一个下标从 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 只包含小写英文字母。

方法一：模拟

首先开辟一个大小为26的数组$bin$，用来存放26个字母的出现次数（只需要遍历一遍字符串即可得到）

接着用$i$从0遍历到26，如果$bin[i]$非零，就让$bin[i]$减去$1$，如果其余非零的bin值全部相同就返回$true$

如果遍历完也没有返回$true$，就返回$false$

怎么判断非零bin的值是否全部相等呢？使用一个变量$val=0$，遍历$bin$。

• 如果$bin[i]$非零，就看$val$是否为$0$
  • 如果$val$为$0$，就令$val=bin[i]$
  • 否则若$val\ne bin[i]$，就返回$false$

若遍历完未返回$false$，就返回$true$

• 时间复杂度 O ( l e n ( w o r d ) C 2 ) O(len(word) C^2) O(len(word) C2)，其中$C=26$
• 空间复杂度$O(C)$

AC代码

C

C 时间击败100%，空间击败93.22%嘿嘿，没有使用自带哈希表

class Solution {
private:
    bool isSame(int* a) {
        int val = 0;
        for (int i = 0; i < 26; i  ) {
            if (a[i]) {
                if (val) {
                    if (a[i] != val) {
                        return false;
                    }
                }
                else {
                    val = a[i];
                }
            }
        }
        return true;
    }
public:
    bool equalFrequency(string word) {
        int bin[26] = {0};
        for (char c : word) {
            bin[c - 'a']  ;
        }
        for (int i = 0; i < 26; i  ) {
            if (bin[i]) {
                bin[i]--;
                if (isSame(bin)) {
                    return true;
                }
                bin[i]  ;
            }
        }
        return false;
    }
};

Python

class Solution:
    def isSame(self, a: list) -> bool:
        val = 0
        for v in a:
            if v:
                if val:
                    if val != v:
                        return False
                else:
                    val = v
        return True
    
    def equalFrequency(self, word: str) -> bool:
        bin = [0] * 26
        for c in word:
            bin[ord(c) - ord('a')]  = 1
        for i in range(26):
            if bin[i]:
                bin[i] -= 1
                if self.isSame(bin):
                    return True
                bin[i]  = 1
        return False

这篇好文章是转载于：学新通技术网