LeetCode 2423 - Remove Letter To Equalize Frequency

The problem asks us to determine if we can remove exactly one character from a string word such that all remaining characters in the string have the same frequency. The input string consists of lowercase English letters and has a length between 2 and 100.

leetcodeeasyhash-tablestringcounting

LeetCode Problem 2423

Difficulty: 🟢 Easy
Topics: Hash Table, String, Counting

Solution

Problem Understanding

The problem asks us to determine if we can remove exactly one character from a string word such that all remaining characters in the string have the same frequency. The input string consists of lowercase English letters and has a length between 2 and 100. The output is a boolean indicating whether this transformation is possible.

Restating it, we need to check if deleting a single character can make the counts of all distinct characters equal. The input string may contain multiple characters with varying frequencies, and we must remove exactly one character, meaning doing nothing is not an option.

Important edge cases include strings where:

  • All characters already have the same frequency except for one character.
  • Only one character occurs once, and removing it balances frequencies.
  • Removing any character cannot equalize frequencies due to multiple discrepancies.
  • The string has only two characters, which is the minimal length.

The constraints are small (word.length <= 100), which allows approaches with O(n²) complexity if necessary, though a linear solution is achievable.

Approaches

Brute Force

The brute-force approach iterates over every character in the string, removes it, and checks if the resulting string has all characters with equal frequency. For each removal, we can use a frequency counter and verify if all counts are equal. This guarantees correctness because it explicitly checks all possibilities. The downside is that this approach requires O(n²) time due to recalculating frequencies for each of the n removals, which is unnecessary given the small constraints.

Optimal Approach

The key insight is that we do not need to simulate every removal. Instead, we can count the frequency of each character once, then analyze the frequency counts:

  1. Count how many times each character appears using a hash map.
  2. Count the occurrences of these frequencies using another hash map.
  3. There are only a few scenarios where removing a single character will balance frequencies:
  • One character occurs exactly once and can be removed.
  • One character occurs one more time than the others; removing one instance balances the counts.
  • All characters already have equal frequency except one character that occurs once.

By examining the distribution of frequencies and their counts, we can decide in O(n) time whether it is possible to remove a single character to equalize the frequencies.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Remove each character and check frequencies explicitly
Optimal O(n) O(1) Count frequencies and analyze frequency distribution without removing characters

Algorithm Walkthrough

  1. Create a hash map freq to count the occurrences of each character in word.
  2. Create another hash map countFreq to count how many characters have each frequency.
  3. If countFreq has only one key and that key is 1, return true (all characters are unique, removing any character leaves equal frequencies).
  4. If countFreq has exactly two keys, check two possibilities:
  • One frequency is 1 and occurs once (we can remove that character entirely).
  • The other frequency is exactly 1 higher than the other, and occurs once (we can remove one instance of that character).
  1. In all other cases, return false because no single removal can equalize the frequencies.

Why it works: The algorithm works because for a single removal to balance frequencies, the frequency counts can only differ by at most 1, and one of the frequencies must occur exactly once. By checking the frequency distribution, we efficiently determine if such a removal exists.

Python Solution

class Solution:
    def equalFrequency(self, word: str) -> bool:
        from collections import Counter
        
        freq = Counter(word)
        countFreq = Counter(freq.values())
        
        if len(countFreq) == 1:
            # Case: all characters have the same frequency
            key = list(countFreq.keys())[0]
            if key == 1 or len(freq) == 1:
                return True
            return False
        
        if len(countFreq) == 2:
            f1, f2 = countFreq.keys()
            c1, c2 = countFreq[f1], countFreq[f2]
            
            # Case 1: One frequency is 1 and occurs once
            if (f1 == 1 and c1 == 1) or (f2 == 1 and c2 == 1):
                return True
            
            # Case 2: One frequency is higher by 1 and occurs once
            if (f1 - f2 == 1 and c1 == 1) or (f2 - f1 == 1 and c2 == 1):
                return True
        
        return False

The Python code first counts the frequency of each character and then counts how many characters share each frequency. By analyzing the number of distinct frequencies and their counts, we efficiently check the two scenarios where removing a single character can balance the frequencies.

Go Solution

func equalFrequency(word string) bool {
    freq := make(map[rune]int)
    for _, ch := range word {
        freq[ch]++
    }

    countFreq := make(map[int]int)
    for _, v := range freq {
        countFreq[v]++
    }

    if len(countFreq) == 1 {
        for k := range countFreq {
            if k == 1 || len(freq) == 1 {
                return true
            }
        }
        return false
    }

    if len(countFreq) == 2 {
        var f1, f2, c1, c2 int
        i := 0
        for k, v := range countFreq {
            if i == 0 {
                f1, c1 = k, v
            } else {
                f2, c2 = k, v
            }
            i++
        }

        if (f1 == 1 && c1 == 1) || (f2 == 1 && c2 == 1) {
            return true
        }

        if (f1-f2 == 1 && c1 == 1) || (f2-f1 == 1 && c2 == 1) {
            return true
        }
    }

    return false
}

The Go implementation mirrors the Python logic. The main differences are iterating over maps, which in Go has no guaranteed order, and handling integer keys and values explicitly.

Worked Examples

Example 1: word = "abcc"

  • Count characters: {'a':1, 'b':1, 'c':2}
  • Count frequencies: {1:2, 2:1}
  • Two frequencies exist: 1 occurs 2 times, 2 occurs 1 time
  • Frequency 2 occurs once, removing one 'c' makes all frequencies equal to 1
  • Return true

Example 2: word = "aazz"

  • Count characters: {'a':2, 'z':2}
  • Count frequencies: {2:2}
  • Only one frequency exists (2), cannot remove a single character to equalize
  • Return false

Complexity Analysis

Measure Complexity Explanation
Time O(n) Count character frequencies and count frequency occurrences, each O(n)
Space O(1) Maximum 26 characters for lowercase English letters, constant space

The reasoning is that n is at most 100, so the hash maps store a constant number of keys at most 26, leading to effectively O(1) space.

Test Cases

# Provided examples
assert Solution().equalFrequency("abcc") == True  # Removing one 'c' balances frequencies
assert Solution().equalFrequency("aazz") == False # No single removal balances frequencies

# Additional cases
assert Solution().equalFrequency("a") == True     # Single character, removing it balances (trivial)
assert Solution().equalFrequency("aa") == True    # Two identical characters, removing one leaves equal frequency
assert Solution().equalFrequency("abc") == True   # All characters frequency 1, removing any still balanced
assert Solution().equalFrequency("aabbcc") == False # Removing any character does not balance
assert Solution().equalFrequency("aaab") == True  # Remove one 'a', all remaining have frequency 1
Test Why
"abcc" Removing 'c' balances frequencies
"aazz" No single removal balances frequencies
"a" Edge case, single character
"aa" Two characters same frequency
"abc" All frequencies 1, removing any leaves balance
"aabbcc" Multiple characters, cannot balance by removing one
"aaab" One character occurs more, removing one instance balances

Edge Cases

  1. Single character string: "a" - Removing it leaves an empty string, which is trivially balanced. Handled by checking if frequency key is 1.
  2. All characters occur exactly once: "abc" - Removing any character still results in equal frequency for the rest. Handled because the frequency map shows counts of 1.
  3. One character occurs much more than others: "aaab" - The algorithm detects that removing one occurrence of the character with higher frequency balances the rest.

These edge cases ensure that the implementation correctly handles strings where removal affects either rare or frequent characters and that the analysis of frequency counts is robust.