Abstract / Summary

Remove one letter so all remaining letters have the same frequency.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 20% (400k+ submissions).

Typical patterns to solve this problem:

• Counting
• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The equalFrequency method determines whether a given string can be transformed into a state where every character appears the same number of times by removing exactly one character occurrence. The algorithm proceeds by counting character frequencies, summarizing how many characters share each frequency, and then evaluating a small set of logical conditions that capture all viable scenarios.

Building the character frequency map

The first phase iterates over the input string and records how many times each distinct character occurs. A defaultdict of integers is used so that each new character is automatically initialized to zero before being incremented.

freq = defaultdict(int)
for c in word:
    freq[c] += 1

This single pass creates a mapping from characters to their occurrence counts.

Summarizing frequency distribution

A second dictionary, also a defaultdict(int), aggregates how many characters share the same count. By iterating over the values of the first dictionary, the code builds a frequency-of-frequencies map.

ff = defaultdict(int)
for f in freq:
    ff[freq[f]] += 1

The resulting structure tells, for example, that three different characters each appear twice, while one character appears five times.

Determining extreme frequencies

The algorithm extracts the highest and lowest occurrence counts among all characters. These extremes are used in the subsequent logical checks.

high = max(freq.values())
low  = min(freq.values())

Handling the single-character case

If the input consists of only one distinct character, any removal leaves a uniform frequency (either zero or one). The code captures this with a direct length check.

if len(freq) == 1:
    return True

All characters appear once

When every character occurs exactly once, removing any one character still leaves a uniform frequency of one for the remaining characters. This situation is identified by checking that there is only one entry in the frequency-of-frequencies map and that the common frequency equals one.

if len(ff) == 1 and high == 1:
    return True

Removing the most frequent character

One viable transformation is to delete a single occurrence of the character that appears most often, thereby reducing its count to match the others. This is possible when there are exactly two distinct frequencies, the higher frequency occurs for only one character, and it exceeds the lower frequency by exactly one.

if len(ff) == 2 and ff[high] == 1 and high == low + 1:
    return True

Removing the least frequent character

Another valid scenario is to eliminate the sole occurrence of a character that appears only once, leaving all remaining characters with the same higher frequency. The condition checks for two distinct frequencies, that the lower frequency occurs for a single character, and that this lower frequency equals one.

if len(ff) == 2 and ff[low] == 1 and low == 1:
    return True

Default outcome

If none of the specific patterns match, the method concludes that a single removal cannot achieve uniform frequencies and returns False.

return False

Edge Cases Addressed

The implementation explicitly covers the situation where the input string contains only one unique character, guaranteeing a True result regardless of length. It also handles the case where every character appears exactly once, which is a borderline scenario because the removal of any character still satisfies the uniformity requirement. Additionally, the logic for removing either the most frequent or the least frequent character ensures that cases with a single outlier frequency are correctly identified, even when that outlier differs by only one occurrence from the rest.

Performance Optimizations

The code leverages defaultdict to avoid explicit existence checks during frequency updates, resulting in constant-time increments. The construction of the two dictionaries is performed in linear passes over the input string and the set of distinct characters, respectively, minimizing overhead. Computing the maximum and minimum frequencies uses built-in functions that operate directly on the dictionary’s value view, avoiding manual iteration. By reducing the decision logic to a handful of boolean expressions that involve only the size of the frequency-of-frequencies map and the extreme values, the algorithm avoids any nested loops or expensive recomputation, ensuring that the overall execution scales efficiently with the length of the input string.

Imagine gathering a giant pile of colorful building blocks of all different shapes. This code acts like a tiny helper that looks at your blocks to see if they can be organized into a perfectly balanced set. First, the code counts how many times each specific shape appears in your pile. It puts those counts into a little notebook so it remembers exactly how many of each block you have. Then, it checks the notebook to see if the groups of blocks match up. Maybe every color has the same number of blocks, or maybe removing just one block would make all the groups equal. The code walks through a few special tricks to see if your collection is already balanced or if it could become balanced by taking away one single piece. If a balance is found using those tricks, the code gives a thumbs up. If nothing works, it just looks for another way to organize the pile.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java			C++		Python	TS
	WalkCCC	Java			C++		Python
	leetcode.ca	Java			C++	Go	Python	TS
	Progiez	Java			C++		Python
github	charles-wangkai	Java
	everthis			JS
	fartem		Ruby
	fsq				C++
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
varunu28	Java

This easy problem has the lowest acceptance rate of just 20%.

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality