We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Letter To Equalize Frequency

Number: 2532

Difficulty: Easy

Paid? No

Companies: Bloomberg, Google, Walmart Labs, tcs

Problem Description

Given a string "word" consisting of lowercase English letters, remove exactly one letter such that the frequency of every letter present in the remaining word becomes equal. Return true if such removal is possible; otherwise, return false.

Key Insights

  • Use a hash table (dictionary) to count the frequency of each letter.
  • Since only one removal is allowed, simulate the removal for each unique letter type and check if the remaining frequencies are all equal.
  • If a letter's count becomes zero after removal, remove it from the frequency map before checking equality.
  • Due to the small constraints (word length at most 100 and only 26 possible letters), a simulation approach is efficient.

Space and Time Complexity

Time Complexity: O(U) where U is the number of unique characters (at most 26), since we simulate removal for each letter type. Space Complexity: O(U) for storing the frequency count.

Solution

We first count the frequency of each letter in the given word. For each unique letter, we simulate its removal by decrementing its count. If the count becomes zero, we remove that letter from the frequency map. Then we check if all remaining letters have the same frequency. If at least one simulation results in equal frequency for all letters, we return true. Otherwise, we return false.

Code Solutions

# Python solution with detailed comments

def equalFrequency(word: str) -> bool:
    # Build frequency dictionary for the given word
    freq = {}
    for ch in word:
        freq[ch] = freq.get(ch, 0) + 1

    # Check each unique letter for removal possibility
    for letter in freq:
        # Copy the frequency dictionary for simulation
        freq_copy = freq.copy()
        # Decrement the frequency of the chosen letter by one
        freq_copy[letter] -= 1
        # Remove letter from dictionary if frequency is zero
        if freq_copy[letter] == 0:
            del freq_copy[letter]
        
        # Get a set of all frequency values from the remaining letters
        freq_values = list(freq_copy.values())
        # Check if all frequencies are equal; note that the list isn't empty since word length >= 2 after removal
        if len(set(freq_values)) == 1:
            return True

    return False

# Example usage:
print(equalFrequency("abcc"))  # Expected output: True
print(equalFrequency("aazz"))  # Expected output: False
← Back to All Questions