Problem Description

You have a string word consisting of lowercase English letters. Your task is to determine if you can remove exactly one letter from the string so that all remaining letters appear with the same frequency.

The problem requires you to:

1. Select one index in the string
2. Remove the letter at that index
3. Check if all letters that remain in the string have equal frequencies

A letter's frequency is simply how many times it appears in the string. You must remove exactly one letter - you cannot choose to remove nothing.

For example:

• If you have the string "aabb", you can remove one 'a' to get "abb", where both 'a' and 'b' appear exactly once (frequency of 1), making this valid
• If you have "abc", removing any letter leaves two different letters each appearing once, which is equal frequency

The function should return true if such a removal is possible, and false otherwise.

The solution approach iterates through each unique letter in the string, temporarily reduces its count by 1, and checks if all non-zero letter frequencies become equal. If any letter's removal achieves this, the function returns true. The key insight is using set(v for v in cnt.values() if v) to check if all non-zero frequencies are the same - if this set has only one element, all frequencies are equal.

Intuition

When we need to check if removing one letter makes all frequencies equal, the key insight is that we need to try removing each letter and see what happens. Instead of actually removing letters from the string and recounting everything (which would be inefficient), we can use a smarter approach.

First, let's count how often each letter appears in the original string. Now, to simulate removing a letter, we can simply decrease its count by 1 temporarily. This is much faster than rebuilding the string.

The critical observation is that after removing one occurrence of a letter, we need to check if all remaining letters have the same frequency. But how do we check this efficiently? If we look at all the frequency values (ignoring letters with frequency 0 since they don't exist in the string anymore), they should all be the same number.

Here's where the elegant trick comes in: we can collect all non-zero frequencies into a set. Since a set only contains unique values, if all frequencies are the same, the set will have exactly one element. For example, if our frequencies are [2, 2, 2, 0], the set of non-zero values would be {2}, which has size 1.

So our strategy becomes:

1. Count all letter frequencies once at the beginning
2. For each letter that appears in the string, temporarily decrease its count by 1
3. Check if all non-zero frequencies are now the same (by checking if the set of non-zero frequencies has size 1)
4. If yes, we found a valid removal; if not, restore the count and try the next letter

This approach is efficient because we only need to count the letters once, and then we're just doing simple arithmetic operations and set checks for each unique letter in the string.

Solution Approach

The implementation uses a counting and enumeration strategy to solve this problem efficiently.

Step 1: Count Letter Frequencies

cnt = Counter(word)

We use Python's Counter from the collections module to create a hash table that maps each letter to its frequency in the string. This gives us the initial count of all letters in O(n) time.

Step 2: Enumerate and Test Each Letter

for c in cnt.keys():

We iterate through each unique letter that appears in the string. We only need to check letters that actually exist in the string, which is why we iterate through cnt.keys().

Step 3: Simulate Removing One Occurrence

cnt[c] -= 1

For each letter c, we temporarily decrease its count by 1. This simulates removing one occurrence of that letter from the string.

Step 4: Check if All Remaining Frequencies are Equal

if len(set(v for v in cnt.values() if v)) == 1:
    return True

This is the core checking logic:

• cnt.values() gets all frequency values
• v for v in cnt.values() if v filters out zero frequencies (letters that no longer exist after removal)
• set(...) creates a set of these non-zero frequencies
• len(...) == 1 checks if all non-zero frequencies are the same (the set would contain only one unique value)

If the check passes, we immediately return True since we found a valid removal.

Step 5: Restore and Continue

cnt[c] += 1

If the current letter doesn't work, we restore its original count by adding 1 back, then continue to test the next letter.

Step 6: Return False if No Valid Removal Found

return False

If we've tested all letters and none of them resulted in equal frequencies when removed, we return False.

The time complexity is O(n + k²) where n is the length of the string and k is the number of unique letters (at most 26). The space complexity is O(k) for storing the frequency counter.

Example Walkthrough

Let's walk through the solution with the string word = "abcc".

Step 1: Count Letter Frequencies First, we count each letter's frequency:

• 'a': 1
• 'b': 1
• 'c': 2 So cnt = {'a': 1, 'b': 1, 'c': 2}

Step 2: Try Removing Each Letter

Attempt 1 - Remove one 'a':

• Temporarily set cnt['a'] = 0 (1 - 1 = 0)
• Current frequencies: {'a': 0, 'b': 1, 'c': 2}
• Non-zero frequencies: {1, 2}
• Since the set has 2 elements (not 1), frequencies are NOT equal
• Restore: cnt['a'] = 1

Attempt 2 - Remove one 'b':

• Temporarily set cnt['b'] = 0 (1 - 1 = 0)
• Current frequencies: {'a': 1, 'b': 0, 'c': 2}
• Non-zero frequencies: {1, 2}
• Since the set has 2 elements (not 1), frequencies are NOT equal
• Restore: cnt['b'] = 1

Attempt 3 - Remove one 'c':

• Temporarily set cnt['c'] = 1 (2 - 1 = 1)
• Current frequencies: {'a': 1, 'b': 1, 'c': 1}
• Non-zero frequencies: {1}
• Since the set has exactly 1 element, all frequencies ARE equal!
• Return True

The function returns True because removing one 'c' from "abcc" gives us "abc", where each letter appears exactly once (equal frequency of 1).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + C^2)

The algorithm first creates a frequency counter using Counter(word), which takes O(n) time where n is the length of the string. Then, it iterates through each unique character in the counter (at most C characters where C = 26 for lowercase English letters). For each iteration:

• Decrementing cnt[c] takes O(1)
• Creating a set from filtered counter values takes O(C) time (iterating through all counter values)
• Checking the set length takes O(1)
• Incrementing cnt[c] back takes O(1)

Since we iterate C times and each iteration takes O(C) time, the loop contributes O(C^2) to the complexity. Therefore, the total time complexity is O(n + C^2).

Space Complexity: O(C)

The space is primarily used by the Counter object which stores at most C unique characters and their frequencies. The temporary set created in each iteration also uses at most O(C) space, but this doesn't increase the overall space complexity. Therefore, the space complexity is O(C) where C = 26.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Handling Edge Cases with All Same Characters

The Problem: When the input string contains all identical characters (e.g., "aaaa"), removing one character still leaves all remaining characters with equal frequency. However, some implementations might incorrectly handle this case if they don't properly filter zero frequencies or if they have special case logic that breaks down.

Example:

• Input: "aaaa"
• After removing one 'a': "aaa"
• All remaining 'a's have frequency 3 (equal)
• Should return true

Solution: The current implementation handles this correctly by filtering out zero values (if freq > 0), but ensure you don't add unnecessary special case checks that might break this scenario.

Pitfall 2: Forgetting to Restore the Counter

The Problem: A critical bug occurs if you forget to restore the character count after testing each removal. Without restoration, subsequent iterations work with corrupted frequency data.

Incorrect Code:

for char in char_freq.keys():
    char_freq[char] -= 1
    if len(set(freq for freq in char_freq.values() if freq > 0)) == 1:
        return True
    # Missing: char_freq[char] += 1

Solution: Always restore the counter after each test:

for char in char_freq.keys():
    char_freq[char] -= 1
    if len(set(freq for freq in char_freq.values() if freq > 0)) == 1:
        return True
    char_freq[char] += 1  # Critical restoration step

Pitfall 3: Including Zero Frequencies in the Equality Check

The Problem: After removing a character, if its frequency becomes 0, you shouldn't include it when checking if all frequencies are equal. Including zeros would incorrectly fail valid cases.

Example:

• Input: "abc"
• Remove 'a': frequencies become {'a': 0, 'b': 1, 'c': 1}
• Without filtering: set([0, 1, 1]) has 2 unique values → incorrectly returns false
• With filtering: set([1, 1]) has 1 unique value → correctly returns true

Solution: Always filter out zero frequencies:

non_zero_frequencies = [freq for freq in char_freq.values() if freq > 0]

Pitfall 4: Modifying Dictionary During Iteration

The Problem: Some might try to optimize by actually removing characters from the Counter when their frequency reaches 0, but modifying a dictionary while iterating over it can cause runtime errors or undefined behavior.

Incorrect Approach:

for char in char_freq.keys():  # RuntimeError if dictionary changes size
    char_freq[char] -= 1
    if char_freq[char] == 0:
        del char_freq[char]  # Don't do this!

Solution: Keep the dictionary structure intact and use filtering instead:

for char in list(char_freq.keys()):  # Create a list copy if you must modify
    # Or better: just filter zeros when checking, don't delete
    char_freq[char] -= 1
    non_zero = [v for v in char_freq.values() if v > 0]
    # ... rest of logic
    char_freq[char] += 1