Abstract / Summary

Find the least changes needed to make all characters in a string the same or all even or all odd positions the same.

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 38% (40k+ submissions).

Typical patterns to solve this problem:

• Counting
• Hash Table
• Prefix Sum
• 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 minCharacters method determines the smallest number of character replacements required so that two input strings a and b satisfy one of three possible ordering constraints. The constraints are: every character in a is strictly smaller than every character in b; the opposite ordering; or both strings consist of a single repeated character (the same character for both strings). The algorithm works by converting each string into a frequency histogram, evaluating the three constraints, and returning the minimal edit count.

Frequency Counting

The first phase builds a 26-element list for each string, where each slot holds the count of a particular lowercase English letter.

freqA = [0] * 26
for c in a:
    freqA[ord(c) - 97] += 1
freqB = [0] * 26
for c in b:
    freqB[ord(c) - 97] += 1

Using a fixed-size list avoids dictionary overhead and provides O(1) access for each character. The ord conversion maps 'a'-'z' to indices 0-25.

Evaluating the “Less-Than” Condition

A nested helper, less(one, two), computes the minimal changes needed to make every character in one strictly smaller than every character in two. It iterates over possible split points (threshold) between the two alphabets. For each split, it sums the counts of letters that lie on the wrong side of the threshold and keeps the smallest total.

def less(one, two):
    best = +inf
    for threshold in range(1, 26):
        low  = sum(one[:threshold])
        high = sum(two[threshold:])
        best = min(best, low + high)
    return best

The loop runs 25 times, each iteration performing two slice-based sum operations. Because the slices are small and the list size is constant, the cost remains bounded and independent of the input lengths.

Combining the Two Directions

The algorithm must consider both possible orderings (a < b and b < a). It calls less twice, swapping the frequency arrays, and records the smaller result.

result = min(less(freqA, freqB), less(freqB, freqA))

This captures the optimal edit count for the first two constraints.

Uniform-Character Condition

The third constraint requires both strings to become repetitions of the same single character. The total number of characters that already match a given letter is one + two for each alphabet slot. The needed changes equal the total length minus this match count. The loop evaluates every letter and updates the global minimum.

need = len(a) + len(b)
for one, two in zip(freqA, freqB):
    have = one + two
    result = min(result, need - have)

Using zip iterates over the two frequency lists in lockstep, avoiding separate index handling.

Edge Cases Handled

When either input string is empty, the frequency arrays contain only zeros for that string. The less function still processes thresholds, and the uniform-character loop correctly computes that all characters must be changed to match the non-empty string’s letters, yielding the appropriate edit count.

If both strings consist entirely of a single repeated character (e.g., "aaa" and "aaa"), the uniform-character loop finds a have value equal to the total length, resulting in zero required changes.

When all characters of one string are already smaller than every character of the other (e.g., "abc" and "def"), the less helper discovers a threshold where low and high are both zero, producing a result of zero without any modifications.

The algorithm also gracefully handles the case where the strings contain the full alphabet distribution; the slice sums correctly account for any distribution, and the minimal edit count is derived from the optimal split point.

Performance Optimizations

The implementation relies on fixed-size arrays of length 26, guaranteeing constant-time indexing and eliminating dynamic resizing. Pre-allocating the lists with [0] * 26 avoids repeated append operations.

The use of sum on slices leverages Python’s C-level loop for small, contiguous memory regions, which is faster than manual iteration in pure Python.

The helper less computes the best split in a single pass over the 25 possible thresholds, avoiding nested loops or repeated recomputation of cumulative counts.

The final uniform-character evaluation uses zip to traverse both frequency arrays simultaneously, reducing the number of passes over the data.

Overall, the algorithm’s work scales with the constant alphabet size rather than the length of the input strings, ensuring efficient execution even for very long inputs.

Imagine there are two big boxes filled with colorful letter blocks. Each box has a set of blocks from a to z. Some letters show up a lot and some do not show up at all. The goal is to make the boxes follow certain rules by either changing the letters on the blocks or taking them away until the rules are met.

First, the code counts exactly how many of each letter are in the first box and the second box. It stores these counts in two neat lists so it knows the inventory of letters.

Then, there is a special tool called less that looks at the boxes in two different ways. It picks a spot in the alphabet and tries to make all the letters in the first box come before that spot, while making all the letters in the second box come after that same spot. It checks every possible spot to see which one requires moving the fewest blocks. It does this once for the first box and again for the second box to see which way is better.

Finally, the code checks a rule where every single block in both boxes must turn into the exact same letter. To do this, it counts how many blocks would need to change if every block became an a, then a b, and so on, all the way to z. It keeps track of the smallest number of changes needed to finish the task.

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	C++		Java			Python	TS
	WalkCCC	C++		Java
	leetcode.ca	C++		Java		Go	Python	TS
	Progiez	C++		Java			Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	suxrobGM				C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
suxrobGM	C#
wisdompeak	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