Remove Letter To Equalize Frequency

Easy

Google

2 views

Topics:

Strings

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 x is 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 <= 100
word consists of lowercase English letters only.

Remove Letter To Equalize Frequency

Easy

Google

2 views

Topics:

Strings

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 x is 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 <= 100
word consists of lowercase English letters only.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected data type and range of values in the input string?
Is an empty string a valid input, and if so, what should the output be?
If there are multiple letters that can be removed to equalize frequency, should I return true if *any* of them work?
Is the input string case-sensitive (e.g., should 'A' and 'a' be treated as the same character)?
What constitutes an 'equal frequency'? Does an empty string after removing a letter count as all characters having equal frequency (specifically, zero frequency)?

Brute Force Solution

Approach

The brute force approach to solving this problem is simple: we'll try removing each letter one by one and then check if the resulting word meets the desired condition. If it does, we've found a solution. If none of the letters satisfy the condition when removed, then the answer is false.

Here's how the algorithm would work step-by-step:

Take the given word.
Try removing the first letter and see if the frequencies of the remaining letters are all the same. If so, we're done!
Put the first letter back.
Now, try removing the second letter and check if the frequencies of the remaining letters are all the same. If so, we're done!
Put the second letter back.
Keep doing this, trying to remove each letter in the word, one at a time. After each removal, check if all the remaining letters occur with the same frequency.
If you go through all the letters and none of the removals result in equal frequencies, then it's not possible to achieve equal frequency by removing just one letter, so the answer is no.

Code Implementation

def remove_letter_to_equalize_frequency(word):
    for index_to_remove in range(len(word)):
        # Create a new string with the character at index removed
        modified_word = word[:index_to_remove] + word[index_to_remove+1:]

        # Count the frequency of each character in the modified word
        frequency_counts = {}
        for char in modified_word:
            frequency_counts[char] = frequency_counts.get(char, 0) + 1

        # If the modified word is empty, return True
        if not frequency_counts:
            return True

        # Check if all the frequencies are equal
        first_frequency = list(frequency_counts.values())[0]

        # Early exit if freqs are not the same
        frequencies_are_equal = all(frequency == first_frequency for frequency in frequency_counts.values())
        if frequencies_are_equal:
            return True

    # If no removal results in equal frequencies, return False
    return False

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through each of the n characters of the input string. For each character, it removes the character and then checks if the frequencies of the remaining characters are equal. Checking the frequencies requires iterating through the (n-1) remaining characters to count frequencies and then iterating through the distinct character counts. Therefore, for each of the n characters, we perform an O(n) operation to check the frequencies. This results in a total time complexity of O(n * n), which simplifies to O(n^2).

Space Complexity

O(1) – The provided brute force algorithm iterates through the word and temporarily removes each letter. To check the frequencies after removal, it implicitly creates a frequency count. The maximum number of distinct characters in the word can be at most 26 (all lowercase letters). Therefore, the frequency count data structure will have a maximum size of 26, independent of the input word's length, N. Thus, the auxiliary space used is constant.

Optimal Solution

Approach

To equalize the frequency of all characters by removing just one, the best approach is to analyze the frequency of each character in the string. We need to check if removing a single instance of any character can make the frequency of the remaining characters the same.

Here's how the algorithm would work step-by-step:

First, count how many times each letter appears in the string.
Then, go through each unique letter we found in the string.
Imagine we remove one instance of that letter. Recalculate the letter frequencies assuming we removed the letter.
Check if all the remaining letters have the same frequency. If they do, we found a solution, and the answer is yes.
If none of the letters we tried worked, then it's impossible to make all frequencies equal by removing one letter, and the answer is no.

Code Implementation

def remove_letter_to_equalize_frequency(input_string):
    character_counts = {}
    for char in input_string:
        character_counts[char] = character_counts.get(char, 0) + 1

    unique_characters = list(character_counts.keys())

    for char_to_remove in unique_characters:
        temp_counts = character_counts.copy()

        # Simulate removing one instance of the character.
        temp_counts[char_to_remove] -= 1

        if temp_counts[char_to_remove] == 0:
            del temp_counts[char_to_remove]

        if not temp_counts:
            return True

        frequencies = list(temp_counts.values())

        # Check if all remaining characters have the same frequency.
        if len(set(frequencies)) == 1:
            return True

    return False

Big(O) Analysis

Time Complexity

O(n) – First, counting the frequency of each character involves iterating through the string once, which takes O(n) time where n is the length of the string. Then, for each unique character (at most 26, a constant), we simulate removing it and recalculate the frequencies. Recalculating frequencies takes O(n) time in the worst case. Finally, we check if the frequencies are equal, which takes at most O(n) time since we have to iterate through the updated frequencies. Because we do this for at most 26 unique characters, we are multiplying O(n) by a constant. Thus, the overall time complexity is dominated by the initial frequency calculation and the potential recalculations in the loop and it simplifies to O(n).

Space Complexity

O(1) – The algorithm primarily uses a frequency count. Since we are dealing with lowercase English letters, the frequency map stores at most 26 key-value pairs. Thus, the space used by the frequency map is constant and does not depend on the length of the input string N. No other significant auxiliary data structures are used, meaning the space complexity remains constant regardless of the input size. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty string	Return true immediately, as an empty string vacuously satisfies the condition since there are no characters to have unequal frequency.
String with a single character	Return true, as removing the only character will result in an empty string with equal frequencies.
String with all characters the same	Return true because removing any single character results in all remaining characters having the same frequency.
Maximum length string with many unique characters	The solution should use a frequency counting data structure (e.g., hash map) to efficiently handle large inputs without exceeding time limits.
String with very high frequency of one character and low frequencies of others	The solution must correctly identify that removing one of the high-frequency characters could potentially equalize the frequencies.
String where removing a character leads to multiple possible equalized frequencies	The problem statement implies only one valid removal needs to be found so the algorithm only needs to return true once a valid removal is found.
String where no character removal can equalize frequencies	The algorithm should return false if after checking all possible removals, no equal frequency state is achieved.
String with characters beyond ASCII (Unicode characters)	Ensure the frequency counting data structure supports Unicode characters and their respective frequency counts.