Abstract / Summary

Change the least number of characters so that all strings have the same number of unique characters.

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 28% (80k+ 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 provided implementation determines whether two strings can be made to have the same number of distinct characters by swapping exactly one character from each string. It builds frequency histograms for both inputs, evaluates a quick feasibility condition, and then exhaustively tries every viable pair of characters to swap, checking the distinct-character count after each simulated exchange.

Frequency Counting

The algorithm begins by converting each character to an index in a 26-element array that represents the English lowercase alphabet. Two separate histograms are populated:

a = ord("a")
freq1 = [0] * 26
for c in word1:
    freq1[ord(c) - a] += 1

freq2 = [0] * 26
for c in word2:
    freq2[ord(c) - a] += 1

These arrays hold the exact occurrence count of every letter in word1 and word2, respectively.

Distinct Count Helper

A small inner function computes how many different letters appear in a given histogram:

def distinct(freq):
    return sum(1 for f in freq if f > 0)

By counting entries with a positive frequency, the function returns the current number of distinct characters for either string.

Early Exit Optimization

Before attempting any swaps, the code checks whether the difference in distinct-character counts exceeds what a single swap can possibly fix. Since swapping can affect at most two distinct letters, a difference larger than two makes the task impossible:

diff = abs(distinct(freq1) - distinct(freq2))
if diff > 2:
    return False

This early return prevents unnecessary work when the strings are already too far apart.

Brute-Force Swap Exploration

The core of the solution iterates over every letter that actually appears in word1 and every letter that appears in word2. For each pair, it simulates moving one occurrence of the first letter from word1 to word2 and one occurrence of the second letter from word2 to word1:

for one in range(len(freq1)):
    if freq1[one] == 0:
        continue
    for two in range(len(freq1)):
        if freq2[two] == 0:
            continue
        freq1[one] -= 1
        freq1[two] += 1
        freq2[one] += 1
        freq2[two] -= 1
        if distinct(freq1) == distinct(freq2):
            return True
        freq1[one] += 1
        freq1[two] -= 1
        freq2[one] -= 1
        freq2[two] += 1

The nested loops ensure that only letters present in the respective strings are considered, avoiding needless iterations over zero-frequency entries.

State Restoration

After each simulated swap, the algorithm restores the original histograms by reversing the modifications. This in-place update and rollback pattern eliminates the need for copying the entire frequency arrays for every trial, keeping memory usage low and avoiding the overhead of repeated allocations.

Edge Cases Handled

The implementation gracefully deals with several boundary conditions:

• When one or both input strings contain only a single distinct character, the distinct-count helper still returns the correct value, and the early exit condition correctly identifies whether a swap could equalize the counts.
• If a string lacks a particular letter, the inner loops skip that index, ensuring that attempts to decrement a zero frequency never occur.
• Swapping a character with itself (i.e., the same letter in both strings) is implicitly covered because the loops allow one and two to refer to the same alphabet index; the net effect on the histograms is neutral, and the distinct-count check will succeed only if the strings were already balanced.
• The early exit handles the scenario where the distinct-character difference is exactly two; the subsequent exhaustive search will find a suitable swap if one exists.

Performance Optimizations

Two notable optimizations are present:

• The early exit based on the absolute difference of distinct counts prunes the search space dramatically for inputs that are far apart, returning immediately without entering the costly double loop.
• By updating the frequency arrays in place and then undoing the changes, the code avoids creating temporary copies for each swap trial. This reduces both allocation overhead and garbage-collection pressure, leading to faster execution especially when the strings are long.

Overall, the solution combines straightforward histogram manipulation with a targeted early-termination check and an efficient in-place simulation of swaps to solve the problem within the constraints of a single character exchange.

Imagine two boxes filled with colorful letter blocks. The goal is to see if swapping one block from the first box with one block from the second box makes both boxes have the exact same number of different colors.

First, the code creates a checklist for each box to keep track of how many of each letter is inside. It counts every block to know exactly what is available.

Then, there is a small trick to save time. If the boxes are already too different, swaping blocks will not fix it, so the code stops early.

Next, the code starts trying out different swaps. It takes one block from the first box and one from the second box and trades their places. After each trade, it looks to see if the new collection of blocks in both boxes has the same variety of colors.

If the trade makes the boxes match, the work is done. If the trade does not help, the code puts the blocks back where they started and tries a different pair. It keeps testing different combinations until it finds a pair that makes the boxes have the same number of unique letter types.

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

not analyzed yet

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
	fsq			C++
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
fsq	C++

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