Remove Letter To Equalize Frequency

Difficulty: Easy | Acceptance: 19.40% | Paid: No Topics: Hash Table, String, Counting

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, otherwise, return false.

• Examples
• Constraints
• Brute Force Simulation
• Frequency Count Analysis

Examples

Example 1:

Input: word = "abcc"
Output: true
Explanation: Select index 3 and delete the letter: 'abcc' -> "abc".
The frequency of 'a', 'b', and 'c' are all 1.

Example 2:

Input: word = "aazz"
Output: false
Explanation: We must delete one character, so either the string becomes "azz" with frequencies {a:1, z:2} or "aaz" with frequencies {a:2, z:1}. Neither have equal frequencies.

Constraints

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

Brute Force Simulation

Intuition Since the string length is small (max 100), we can simulate the removal of every character one by one. For each resulting string, we count the frequency of each character and check if all non-zero frequencies are identical.

Steps

• Iterate through the string from index 0 to n-1.
• For each index i, construct a new string excluding the character at i.
• Calculate the frequency of each character in this new string.
• Check if all non-zero frequencies are the same.
• If a valid configuration is found, return true. If the loop finishes without success, return false.

class Solution:
    def equalFrequency(self, word: str) -> bool:
        n = len(word)
        for i in range(n):
            # Construct new string without char at i
            new_word = word[:i] + word[i+1:]
            # Count frequencies
            counts = {}
            for c in new_word:
                counts[c] = counts.get(c, 0) + 1
            # Check if all frequencies are equal
            vals = list(counts.values())
            if all(v == vals[0] for v in vals):
                return True
        return False

Complexity

• Time: O(n²) where n is the length of the string. We iterate n times, and each iteration takes O(n) to build the string and count frequencies.
• Space: O(1) auxiliary space (excluding the output string), as the frequency array size is fixed at 26.
• Notes: Simple to implement and sufficiently fast given the constraint n <= 100.

Frequency Count Analysis

Intuition Instead of physically removing characters and rebuilding strings, we can work directly with the frequency counts. We iterate through the unique characters present in the string, decrement their count by 1 (simulating removal), and check if the remaining frequencies are all equal.

Steps

• Count the frequency of every character in the original string.
• Iterate through each character present in the frequency map.
• Decrement the count of the current character by 1.
• If the count reaches 0, remove the character from the map.
• Check if the set of remaining frequency values contains only one unique value.
• If yes, return true.
• Restore the count of the current character and continue.
• If the loop finishes, return false.

from collections import Counter

class Solution:
    def equalFrequency(self, word: str) -> bool:
        freq = Counter(word)
        for c in freq:
            # Simulate removal
            freq[c] -= 1
            if freq[c] == 0:
                del freq[c]
            # Check if remaining frequencies are equal
            if len(set(freq.values())) == 1:
                return True
            # Backtrack
            freq[c] = freq.get(c, 0) + 1
        return False

Complexity

• Time: O(n) where n is the length of the string. We iterate through the string once to build counts, and then iterate through the constant 26-letter alphabet.
• Space: O(1) auxiliary space, as the storage size is fixed (26 integers).
• Notes: More efficient than the brute force approach, especially if the string length were larger.