Problem

You are given a 0-indexed string word, consisting of lowercase English letters. You need to select one index and remove the letter at that index from word so that the frequency of every letter present in word is equal.

Return __true if it is possible to remove one letter so that the frequency of all letters inword are equal, andfalse otherwise.

Note:

  • The frequency of a letter x is the number of times it occurs in the string.
  • You must remove exactly one letter and cannot choose to do nothing.

Examples

Example 1

1
2
3

Input: word = "abcc"
Output: true
Explanation: Select index 3 and delete it: word becomes "abc" and each character has a frequency of 1.

Example 2

1
2
3

Input: word = "aazz"
Output: false
Explanation: We must delete a character, so either the frequency of "a" is 1 and the frequency of "z" is 2, or vice versa. It is impossible to make all present letters have equal frequency.

Constraints

  • 2 <= word.length <= 100
  • word consists of lowercase English letters only.

Solution

Method 1 - Try Removing Each Letter

Intuition

We want to check if removing one letter can make all remaining letter frequencies equal. Try removing each letter and check the frequencies.

Approach

  1. Count the frequency of each letter.
  2. For each unique letter, try removing one occurrence and check if the remaining frequencies (ignoring zeros) are all equal.
  3. If any removal works, return true; else, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;

bool equalFrequency(string word) {
    unordered_map<char, int> freq;
    for (char c : word) freq[c]++;
    for (auto& [ch, cnt] : freq) {
        freq[ch]--;
        unordered_set<int> s;
        for (auto& [_, v] : freq) if (v > 0) s.insert(v);
        if (s.size() == 1) return true;
        freq[ch]++;
    }
    return false;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func equalFrequency(word string) bool {
    freq := make(map[rune]int)
    for _, c := range word {
        freq[c]++
    }
    for ch := range freq {
        freq[ch]--
        s := map[int]struct{}{}
        for _, v := range freq {
            if v > 0 {
                s[v] = struct{}{}
            }
        }
        if len(s) == 1 {
            return true
        }
        freq[ch]++
    }
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.*;
public class Solution {
    public boolean equalFrequency(String word) {
        int[] freq = new int[26];
        for (char c : word.toCharArray()) freq[c - 'a']++;
        for (int i = 0; i < 26; i++) {
            if (freq[i] == 0) continue;
            freq[i]--;
            Set<Integer> s = new HashSet<>();
            for (int f : freq) if (f > 0) s.add(f);
            if (s.size() == 1) return true;
            freq[i]++;
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

fun equalFrequency(word: String): Boolean {
    val freq = IntArray(26)
    for (c in word) freq[c - 'a']++
    for (i in 0 until 26) {
        if (freq[i] == 0) continue
        freq[i]--
        val s = mutableSetOf<Int>()
        for (f in freq) if (f > 0) s.add(f)
        if (s.size == 1) return true
        freq[i]++
    }
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def equalFrequency(word: str) -> bool:
    from collections import Counter
    freq = Counter(word)
    for ch in freq:
        freq[ch] -= 1
        vals = [v for v in freq.values() if v > 0]
        if len(set(vals)) == 1:
            return True
        freq[ch] += 1
    return False
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

use std::collections::HashMap;
fn equal_frequency(word: &str) -> bool {
    let mut freq = HashMap::new();
    for c in word.chars() {
        *freq.entry(c).or_insert(0) += 1;
    }
    for (&ch, _) in freq.clone().iter() {
        *freq.get_mut(&ch).unwrap() -= 1;
        let vals: Vec<_> = freq.values().filter(|&&v| v > 0).collect();
        let set: std::collections::HashSet<_> = vals.iter().cloned().collect();
        if set.len() == 1 {
            return true;
        }
        *freq.get_mut(&ch).unwrap() += 1;
    }
    false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function equalFrequency(word: string): boolean {
    const freq: Record<string, number> = {};
    for (const c of word) freq[c] = (freq[c] || 0) + 1;
    for (const ch in freq) {
        freq[ch]--;
        const vals = Object.values(freq).filter(v => v > 0);
        if (new Set(vals).size === 1) return true;
        freq[ch]++;
    }
    return false;
}

Complexity

  • ⏰ Time complexity: O(26 * N), where N is the length of word.
  • 🧺 Space complexity: O(1), since there are at most 26 letters.