algoadvance

You are given a string word. In one operation, you can choose any character of the string and remove it. You need to determine if it’s possible to remove exactly one character so that the frequency of each distinct character in the resulting string becomes the same.

Return true if it’s possible, otherwise return false.

Clarifying Questions

1. Q: What is the range of the length of the string word?
   • A: The length of the string can range from 1 to (10^5).
2. Q: Can word contain any characters other than lowercase English letters?
   • A: No, word consists only of lowercase English letters.
3. Q: What should be returned if word is of length 1?
   • A: If the length of the word is one, there is no character to remove, thus should return false.

Strategy

1. Count Frequencies:
   • Use a dictionary to count the frequency of each character in the string.
2. Frequency of Frequencies:
   • Create another dictionary to count how many characters have the same frequency.
3. Evaluate Conditions:
   • If there is only one frequency, it means all characters already have the same frequency.
   • If there are exactly two different frequencies in the original string, you need to check specific patterns:
     1. One of the frequencies occurs exactly once, and it’s either one more than the other frequency or is 1 (in order to be reduced to balance).
     2. The other frequencies should all match.

Code

from collections import Counter

def equalFrequency(word: str) -> bool:
    # Counting frequency of each character
    freq = Counter(word)
    
    # Counting the frequency of these frequencies
    freq_of_freq = Counter(freq.values())
    
    if len(freq_of_freq) == 1:
        # All characters have the same frequency
        return True
    
    if len(freq_of_freq) == 2:
        # Extract the two frequencies and their counts
        (freq1, count1), (freq2, count2) = freq_of_freq.items()
        
        # Determine which is the higher frequency
        if freq1 > freq2:
            freq1, freq2 = freq2, freq1
            count1, count2 = count2, count1
        
        # Check if we can match frequencies by removing one character
        if (freq2 == freq1 + 1 and count2 == 1) or (freq1 == 1 and count1 == 1):
            return True
    
    return False

Time Complexity

• Counting frequencies: (O(n)), where (n) is the length of the string, as we go through the string once.
• Counting frequency of frequencies: (O(k)), where (k) is the number of unique characters, which is at most 26.
• Overall complexity: (O(n)), because (n) will dominate (k) in practical scenarios.

With this approach, the solution is efficient and accommodates the constraints provided by the problem, ensuring that we can handle the maximum input size effectively.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?