Remove Letter To Equalize Frequency
EasyPrompt
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:
- The frequency of a letter
xis the number of times it occurs in the string. - You must remove exactly one letter and cannot choose to do nothing.
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 <= 100wordconsists of lowercase English letters only.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We iterate through every character in the input string word. For each character, we consider removing it and then check if the remaining characters in the modified string all have the same frequency. If we find any such removal that satisfies the condition, we can immediately return true. If we exhaust all possible single-character removals and none result in equal frequencies, we return false.
Algorithm
- Iterate through each index
iof thewordfrom0toword.length() - 1. - For each
i, create a new temporary stringtempWordby removing the character at that index. - Check if all characters in
tempWordhave the same frequency using a helper function.- The helper function calculates character frequencies for
tempWord. - It finds the frequency of the first character present in
tempWordand sets it astargetFreq. - It then verifies that all other characters present in
tempWordalso have the frequencytargetFreq.
- The helper function calculates character frequencies for
- If the helper function returns
true, it means a valid removal has been found, so we returntruefrom the main function. - If the loop completes without finding any such
i, it means no single removal can satisfy the condition. Returnfalse.
Walkthrough
The algorithm proceeds as follows:
- Loop through each index
ifrom0toword.length() - 1. This represents selecting the character at indexito be removed. - Inside the loop, construct a new temporary string by removing the character at index
i. For example, ifwordis "abcc" andiis 2, the new string is "abc". - Create a helper function, say
areFrequenciesEqual(String s), that checks if all characters present in a stringshave the same frequency.- This function first calculates the frequency of each character in
sand stores them, for instance, in an array of size 26. - It then iterates through these frequencies. It finds the first non-zero frequency and stores it as the target frequency.
- It continues iterating, and if it finds any other non-zero frequency that is different from the target frequency, it returns
false. - If the loop completes without finding any mismatch, it means all present characters have the same frequency, so it returns
true.
- This function first calculates the frequency of each character in
- Call this helper function on the temporary string. If it returns
true, it means we've found a valid removal. We can stop and returntruefrom the main function. - If the loop completes without finding any valid removal, it means it's impossible. We return
false.
class Solution { public boolean equalFrequency(String word) { for (int i = 0; i < word.length(); i++) { // Create a new string with one character removed. StringBuilder sb = new StringBuilder(word); sb.deleteCharAt(i); String tempWord = sb.toString(); if (areFrequenciesEqual(tempWord)) { return true; } } return false; } private boolean areFrequenciesEqual(String s) { if (s.isEmpty()) { return true; } int[] freq = new int[26]; for (char c : s.toCharArray()) { freq[c - 'a']++; } int targetFreq = 0; // Find the frequency of the first character present. for (int count : freq) { if (count > 0) { targetFreq = count; break; } } // Check if all other present characters have the same frequency. for (int count : freq) { if (count > 0 && count != targetFreq) { return false; } } return true; }}Complexity
Time
O(N^2), where N is the length of `word`. The outer loop runs N times. Inside the loop, creating the substring takes O(N) and checking its frequencies also takes O(N). Thus, the total time is N * (O(N) + O(N)) = O(N^2).
Space
O(N), where N is the length of `word`. A temporary string of length N-1 is created in each iteration. The frequency array inside the helper function takes O(1) space as the alphabet size is constant.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the logic of the problem statement, making it intuitive.
Cons
Inefficient due to its quadratic time complexity.
Involves repeated computations, as frequencies are recalculated for each modified string.
Creates many temporary string objects, which can be memory-intensive for very long strings (though not an issue with the given constraints).
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.