Easy

题目描述

给你一个下标从 0 开始的字符串 word，由小写英文字母组成。你需要选择一个下标并从 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 的频次数组。

解题思路

这道题要求我们删除恰好一个字母后，使得剩余字母的频次都相等。我们可以采用暴力枚举的方法：

核心思路：

  1. 枚举删除每个位置的字母，检查删除后是否满足条件
  2. 对于每次删除操作，统计剩余字母的频次
  3. 检查所有非零频次是否相等

具体步骤：

  1. 遍历字符串的每个位置 i，假设删除位置 i 的字母
  2. 统计删除该字母后各字母的频次
  3. 收集所有非零频次，检查是否都相等
  4. 如果找到一个删除位置使得频次都相等，返回 true
  5. 如果所有位置都尝试过仍不满足，返回 false

时间复杂度分析：

  • 外层循环遍历字符串：O(n)
  • 内层统计频次：O(n)
  • 检查频次是否相等：O(26) = O(1)
  • 总体时间复杂度：O(n²)

由于字符串长度最大为 100，这个复杂度完全可以接受。

优化思考： 虽然可以先统计原始频次，然后枚举删除每个字母来优化，但考虑到数据规模较小，暴力解法更加简洁易懂。

代码实现

class Solution {
public:
    bool equalFrequency(string word) {
        int n = word.length();
        
        // Try removing each character
        for (int i = 0; i < n; i++) {
            vector<int> freq(26, 0);
            
            // Count frequency after removing character at index i
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    freq[word[j] - 'a']++;
                }
            }
            
            // Collect all non-zero frequencies
            vector<int> nonZeroFreqs;
            for (int f : freq) {
                if (f > 0) {
                    nonZeroFreqs.push_back(f);
                }
            }
            
            // Check if all non-zero frequencies are equal
            if (!nonZeroFreqs.empty()) {
                bool allEqual = true;
                for (int f : nonZeroFreqs) {
                    if (f != nonZeroFreqs[0]) {
                        allEqual = false;
                        break;
                    }
                }
                if (allEqual) return true;
            }
        }
        
        return false;
    }
};

class Solution:
    def equalFrequency(self, word: str) -> bool:
        n = len(word)
        
        # Try removing each character
        for i in range(n):
            freq = [0] * 26
            
            # Count frequency after removing character at index i
            for j in range(n):
                if i != j:
                    freq[ord(word[j]) - ord('a')] += 1
            
            # Collect all non-zero frequencies
            non_zero_freqs = [f for f in freq if f > 0]
            
            # Check if all non-zero frequencies are equal
            if non_zero_freqs and all(f == non_zero_freqs[0] for f in non_zero_freqs):
                return True
        
        return False

public class Solution {
    public bool EqualFrequency(string word) {
        int n = word.Length;
        
        // Try removing each character
        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            
            // Count frequency after removing character at index i
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    freq[word[j] - 'a']++;
                }
            }
            
            // Collect all non-zero frequencies
            List<int> nonZeroFreqs = new List<int>();
            for (int f = 0; f < 26; f++) {
                if (freq[f] > 0) {
                    nonZeroFreqs.Add(freq[f]);
                }
            }
            
            // Check if all non-zero frequencies are equal
            if (nonZeroFreqs.Count > 0) {
                bool allEqual = true;
                for (int k = 0; k < nonZeroFreqs.Count; k++) {
                    if (nonZeroFreqs[k] != nonZeroFreqs[0]) {
                        allEqual = false;
                        break;
                    }
                }
                if (allEqual) return true;
            }
        }
        
        return false;
    }
}

var equalFrequency = function(word) {
    const freq = {};
    for (let char of word) {
        freq[char] = (freq[char] || 0) + 1;
    }
    
    const counts = Object.values(freq);
    const countFreq = {};
    for (let count of counts) {
        countFreq[count] = (countFreq[count] || 0) + 1;
    }
    
    const uniqueCounts = Object.keys(countFreq).map(Number).sort((a, b) => a - b);
    
    if (uniqueCounts.length === 1) {
        const count = uniqueCounts[0];
        return count === 1 || countFreq[count] === 1;
    }
    
    if (uniqueCounts.length === 2) {
        const [low, high] = uniqueCounts;
        const lowFreq = countFreq[low];
        const highFreq = countFreq[high];
        
        if (low === 1 && lowFreq === 1) return true;
        if (high === low + 1 && highFreq === 1) return true;
        if (low === 1 && high * highFreq === 1) return true;
        
        return false;
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²)
空间复杂度O(1)

说明：

  • 时间复杂度：外层循环 O(n)，内层统计频次 O(n)，检查频次相等 O(26) = O(1)，总体 O(n²)
  • 空间复杂度：使用固定大小的频次数组 O(26) = O(1)

相关题目