Remove Letter To Equalize Frequency solution and explanation
TCS
Google
9 more videos on this problem
Remove Letter To Equalize Frequency || LeetCode Biweekly Contest 88 || LeetCode EasyBinaryMagic · 10:35 · 2K views
2423. Remove Letter To Equalize Frequency (Leetcode Easy)Programming Live with Larry · 8:18 · 2K views
LeetCode 2423 | Remove Letter To Equalize Frequency | Counting Array | JavaSleepy Cracker · 4:37 · 1K views
Leetcode BiWeekly contest 88 - Easy - Remove Letter To Equalize FrequencyPrakhar Agrawal · 6:45 · 954 views
2423. Remove Letter To Equalize Frequency || Leetcode biweekly contest 88 || C++CS warriors · 10:20 · 802 views
Remove Letter To Equalize Frequency #javainterview #twopointers #javaprogramming #leetcode #hashmapCodeVia · 4:10 · 411 views
leetcode 2423. Remove Letter To Equalize Frequency - two solutions: 1. simulation; 2. classify casesCode-Yao · 14:50 · 363 views
LeetCode 2423 - Remove Letter to Equalize Frequency | Simple Python Explanation for BeginnersThe Unleashed · 3:44 · 258 views
leetcode biweekly contest 88 Remove Letter To Equalize FrequencyZiddiCoder · 12:24 · 115 views
2423. Remove Letter To Equalize Frequency | Coding Session | Live Data Structure and Algorithm EventO(1) Software Network · 1:30:15 · 69 views
The 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 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.
Approach overview
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 1: Approach 1: Frequency Map and Validation
This approach involves constructing a frequency map of the letters in the word. By analyzing the frequencies, we can evaluate if removing one instance of a letter can equate the frequency of remaining letters. Check if the remaining frequencies can form a uniform distribution after removing one letter occurrence from the string.
from collections import Counter
def canEqualizeFrequency(word):
freq = Counter(word)
freq_values = Counter(freq.values())
if len(freq_values) == 1:
return True if 1 in freq_values.values() else False
if len(freq_values) == 2:
(f1, c1), (f2, c2) = freq_values.items()
if (f1 - 1 == f2 and c1 == 1) or (f2 - 1 == f1 and c2 == 1):
return True
if (f1 == 1 and c1 == 1) or (f2 == 1 and c2 == 1):
return True
return False
# Example usage
word = "abcc"
print(canEqualizeFrequency(word)) # Output: Trueimport java.util.HashMap;
import java.util.Map;
public class Solution {
public boolean canEqualizeFrequency(String word) {
Map<Character, Integer> freq = new HashMap<>();
for (char c : word.toCharArray())
freq.put(c, freq.getOrDefault(c, 0) + 1);
Map<Integer, Integer> freqValues = new HashMap<>();
for (int f : freq.values()) {
freqValues.put(f, freqValues.getOrDefault(f, 0) + 1);
}
if (freqValues.size() == 1) {
return freqValues.containsKey(1) && freqValues.get(1) == 1;
}
if (freqValues.size() == 2) {
int[] keys = new int[2];
int[] values = new int[2];
int i = 0;
for (Map.Entry<Integer, Integer> entry : freqValues.entrySet()) {
keys[i] = entry.getKey();
values[i] = entry.getValue();
i++;
}
if ((keys[0] - 1 == keys[1] && values[0] == 1) || (keys[1] - 1 == keys[0] && values[1] == 1)) {
return true;
}
if ((keys[0] == 1 && values[0] == 1) || (keys[1] == 1 && values[1] == 1)) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.canEqualizeFrequency("abcc")); // Output: true
}
}The function uses a frequency counter to assess character frequency, then attempts to either bring one count down to match others by removal, or assess if removing a unique single occurrence leads to uniform frequencies.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), considering a fixed constant space of unique letters in the English alphabet.
Approach 2: Approach 2: Direct Simulation
This approach involves simulating the removal of each letter to check if the remaining letters can have uniform frequencies. For each letter, temporarily remove it, recompute frequencies, and see if the remaining ones are equal.
function canEqualizeFrequency(word) {
const freq = Array(26).fill(0);
for (const char of word) {
freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
for (let i = 0; i < 26; i++) {
if (freq[i] === 0) continue;
freq[i]--;
const filtered = freq.filter(x => x > 0);
const uniqueSet = new Set(filtered);
freq[i]++;
if (uniqueSet.size === 1) {
return true;
}
}
return false;
}
console.log(canEqualizeFrequency("abcc")); // Output: true#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool canEqualizeFrequency(const char* word) {
int len = strlen(word);
int freq[26] = {0};
for (int i = 0; i < len; i++) {
freq[word[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (!freq[i]) continue;
freq[i]--;
int uniqueCount = 0;
int baseFreq = 0;
for (int j = 0; j < 26; j++) {
if (freq[j] > 0) {
if (!uniqueCount) {
baseFreq = freq[j];
uniqueCount++;
} else if (freq[j] != baseFreq) {
uniqueCount = 2;
break;
}
}
}
freq[i]++;
if (uniqueCount == 1) {
return true;
}
}
return false;
}
int main() {
printf("%d\n", canEqualizeFrequency("abcc")); // Output: 1 (true)
return 0;
}This JavaScript code uses an array to maintain the frequency count, tries removing one instance of each letter, evaluates the resulting frequency set, and checks for uniform frequency distribution.
Time Complexity: O(n^2), due to internal iteration checks for frequency uniformity.
Space Complexity: O(1), with frequency tracking limited by the fixed alphabet size.
Approach 3: Counting + Enumeration
First, we use a hash table or an array of length 26 named cnt to count the number of occurrences of each letter in the string.
Next, we enumerate the 26 letters. If letter c appears in the string, we decrement its count by one, then check whether the counts of the remaining letters are the same. If they are, return true. Otherwise, increment the count of c by one and continue to enumerate the next letter.
If the enumeration ends, it means that it is impossible to make the counts of the remaining letters the same by deleting one letter, so return false.
The time complexity is O(n + C^2), and the space complexity is O(C). Here, n is the length of the string word, and C is the size of the character set. In this problem, C = 26.
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;
}
};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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Frequency Map and Validation | Time Complexity: O(n), where n is the length of the string. |
| Approach 2: Direct Simulation | Time Complexity: O(n^2), due to internal iteration checks for frequency uniformity. |
| Counting + Enumeration | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Remove Letter To Equalize Frequency easy or hard?
The problem is classified as Easy on LeetCode but can be tricky because you must reason about frequency patterns after a single removal. Once you focus on character counts instead of positions, the solution becomes straightforward with a simple validation check.
Remove Letter To Equalize Frequency Python/Java solution
Both Python and Java solutions typically use a frequency array or hash map to count characters. After building the counts, simulate removing one occurrence of each letter and verify whether the remaining frequencies are equal. This keeps the implementation simple while maintaining O(n) time complexity.
How to solve Remove Letter To Equalize Frequency in O(n)?
First count the frequency of each letter using an array or hash map. Then try decreasing the count of each character once and check if all remaining non-zero frequencies are equal. Because there are at most 26 characters, each validation step is constant time, giving an overall O(n) algorithm.
What is the best approach for Remove Letter To Equalize Frequency?
The most efficient approach uses a frequency map of the 26 lowercase letters and simulates removing one occurrence of each character type. After each simulated removal, check whether all remaining non-zero frequencies match. This runs in O(n) time with O(1) space because the alphabet size is constant.
Is Remove Letter To Equalize Frequency asked at Google/Amazon/Meta?
Frequency manipulation and counting problems like this appear frequently in interviews at companies such as Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern—analyzing character counts with a hash table—is common in string interview questions.
What data structure is used in Remove Letter To Equalize Frequency?
The primary data structure is a hash table or a fixed-size integer array that stores character frequencies. Since the input consists of lowercase English letters, a 26-element array is usually the most efficient representation.
What is the time complexity of Remove Letter To Equalize Frequency?
The optimal solution runs in O(n) time where n is the length of the string. Building the frequency map requires one pass through the string, and validation checks at most 26 characters. Space complexity is O(1) since only a fixed-size frequency array is used.