Question

2423. 删除字符使频率相同

English Version

题目描述

给你一个下标从 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$ 的数组 $cnt$ 统计字符串中每个字母出现的次数。

接下来，枚举 $26$ 个字母，如果字母 $c$ 在字符串中出现过，我们将其出现次数减一，然后判断剩余的字母出现次数是否相同。如果相同，返回 true，否则将 $c$ 的出现次数加一，继续枚举下一个字母。

枚举结束，说明无法通过删除一个字母使得剩余字母出现次数相同，返回 false。

时间复杂度 $O(n + C^2)$，空间复杂度 $O(C)$，其中 $n$ 为字符串 $word$ 的长度，而 $C$ 为字符集的大小，本题中 $C = 26$。

class Solution:
  def equalFrequency(self, word: str) -> bool:
    cnt = Counter(word)
    for c in cnt.keys():
      cnt[c] -= 1
      if len(set(v for v in cnt.values() if v)) == 1:
        return True
      cnt[c] += 1
    return False

class Solution {
  public boolean equalFrequency(String word) {
    int[] cnt = new int[26];
    for (int i = 0; i < word.length(); ++i) {
      ++cnt[word.charAt(i) - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if (cnt[i] > 0) {
        --cnt[i];
        int x = 0;
        boolean ok = true;
        for (int v : cnt) {
          if (v == 0) {
            continue;
          }
          if (x > 0 && v != x) {
            ok = false;
            break;
          }
          x = v;
        }
        if (ok) {
          return true;
        }
        ++cnt[i];
      }
    }
    return false;
  }
}

class Solution {
public:
  bool equalFrequency(string word) {
    int cnt[26]{};
    for (char& c : word) {
      ++cnt[c - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if (cnt[i]) {
        --cnt[i];
        int x = 0;
        bool ok = true;
        for (int v : cnt) {
          if (v == 0) {
            continue;
          }
          if (x && v != x) {
            ok = false;
            break;
          }
          x = v;
        }
        if (ok) {
          return true;
        }
        ++cnt[i];
      }
    }
    return false;
  }
};

func equalFrequency(word string) bool {
  cnt := [26]int{}
  for _, c := range word {
    cnt[c-'a']++
  }
  for i := range cnt {
    if cnt[i] > 0 {
      cnt[i]--
      x := 0
      ok := true
      for _, v := range cnt {
        if v == 0 {
          continue
        }
        if x > 0 && v != x {
          ok = false
          break
        }
        x = v
      }
      if ok {
        return true
      }
      cnt[i]++
    }
  }
  return false
}

function equalFrequency(word: string): boolean {
  const cnt: number[] = new Array(26).fill(0);
  for (const c of word) {
    cnt[c.charCodeAt(0) - 97]++;
  }
  for (let i = 0; i < 26; ++i) {
    if (cnt[i]) {
      cnt[i]--;
      let x = 0;
      let ok = true;
      for (const v of cnt) {
        if (v === 0) {
          continue;
        }
        if (x && v !== x) {
          ok = false;
          break;
        }
        x = v;
      }
      if (ok) {
        return true;
      }
      cnt[i]++;
    }
  }
  return false;
}