Watch 10 video solutions for Remove Letter To Equalize Frequency, a easy level problem involving Hash Table, String, Counting. This walkthrough by BinaryMagic has 2,934 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 in word are equal, and false otherwise.
Note:
x is the number of times it occurs in the string.
Example 1:
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:
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 <= 100word consists of lowercase English letters only.Problem Overview: You are given a string word. The task is to determine whether removing exactly one character can make the frequency of every remaining letter equal. After the removal, all characters that still appear must have identical counts.
Approach 1: Frequency Map and Validation (O(n) time, O(1) space)
Count the frequency of every character using a hash map or fixed array of size 26. Then simulate removing one occurrence of each distinct character. For each simulation, decrease its count by one and check whether the remaining non‑zero frequencies are identical. Validation is simple: iterate through the frequency map and ensure every non‑zero value matches the first seen value. Because the alphabet size is constant, this validation step is bounded by 26 operations. The main cost is building the frequency map from the string, which takes O(n) time with O(1) extra space. This approach works well because it avoids rebuilding the map for every index and only tests each character type once. It relies on efficient counting with a hash table or array.
Approach 2: Direct Simulation (O(n * 26) time, O(1) space)
This method tries removing each character position in the string and checks whether the remaining string has equal frequencies. For every index i, temporarily skip that character and recompute character counts for the rest of the string. After building the counts, verify that all non‑zero frequencies are equal. Because counting requires scanning up to n characters each time and there are n removal attempts, the straightforward version is O(n^2). However, with a fixed 26‑character alphabet you can optimize counting using a reusable array and simple decrements, making the effective complexity closer to O(n * 26). This approach is conceptually simpler and useful when first reasoning about the problem, especially if you think in terms of explicit simulation of the removal step. It mainly uses operations on arrays and concepts from string processing and counting.
Recommended for interviews: The frequency map validation approach is typically what interviewers expect. It shows you recognize that only character frequencies matter, not individual positions. Starting with direct simulation demonstrates understanding of the problem mechanics, but the optimized counting approach shows stronger algorithmic thinking and awareness of constant‑size alphabets.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Map and Validation | O(n) | O(1) | Best general solution when alphabet size is fixed (26 letters) |
| Direct Simulation | O(n * 26) | O(1) | Good for understanding the problem or quick brute-force verification |