Change Minimum Characters to Satisfy One of Three Conditions

You are given two strings a and b consisting of lowercase English letters. In one operation, you can change any character in either string to any lowercase letter. Find the minimum number of operations needed to satisfy one of three conditions:

1. Every letter in a is strictly less than every letter in b.
2. Every letter in b is strictly less than every letter in a.
3. Both a and b consist of only one distinct letter (the same letter).

This is LeetCode 1737: Change Minimum Characters to Satisfy One of Three Conditions, and it is a great exercise in character frequency counting combined with prefix sums.

Why this problem matters

At first glance, the three conditions look unrelated, and you might be tempted to write three separate algorithms. But all three share the same foundation: counting how often each character appears in both strings. Once you have those frequency arrays, each condition reduces to a simple arithmetic expression.

This problem trains you to think in terms of frequency distributions rather than individual characters. That same mindset applies to anagram problems, string matching, and any task where the counts of elements matter more than their positions.

The key insight

All three conditions can be evaluated efficiently once you have the character frequency arrays for a and b.

For condition 3, you want both strings to consist of a single letter c. The cost is the number of characters in a that are not c plus the number of characters in b that are not c. In other words: len(a) + len(b) - freq_a[c] - freq_b[c]. You try all 26 letters and take the minimum.

For conditions 1 and 2, you pick a "boundary" character c (from 'b' through 'z'). For condition 1, every character in a must be strictly less than c, and every character in b must be >= c. The cost is the number of characters in a that are >= c (they need to be changed to something below c) plus the number of characters in b that are < c (they need to be changed to something >= c). Prefix sums over the frequency arrays let you compute these counts in O(1) per boundary.

Condition 2 is the mirror of condition 1: swap the roles of a and b.

The solution

def min_characters(a: str, b: str) -> int:
    freq_a = [0] * 26
    freq_b = [0] * 26
    for ch in a:
        freq_a[ord(ch) - ord('a')] += 1
    for ch in b:
        freq_b[ord(ch) - ord('a')] += 1

    result = float('inf')

    for c in range(26):
        result = min(result, len(a) + len(b) - freq_a[c] - freq_b[c])

    prefix_a, prefix_b = 0, 0
    for c in range(25):
        prefix_a += freq_a[c]
        prefix_b += freq_b[c]
        result = min(result, (len(a) - prefix_a) + prefix_b)
        result = min(result, prefix_a + (len(b) - prefix_b))

    return result

Let's walk through what each piece does.

The first two loops build frequency arrays for a and b. Each array has 26 entries, one per lowercase letter, storing how many times that letter appears.

The first for c in range(26) loop handles condition 3. For each possible letter c, it computes the cost of making every character in both strings equal to c. This is len(a) + len(b) - freq_a[c] - freq_b[c], because you only keep the characters that are already c and change everything else.

The second loop handles conditions 1 and 2 simultaneously. It maintains running prefix sums: prefix_a is the number of characters in a with value <= the current index, and prefix_b is the same for b. At each boundary c (from index 0 through 24, representing the boundary between letter c and letter c+1):

• (len(a) - prefix_a) + prefix_b is the cost for condition 1: change the characters in a that are too large (those >= the boundary) and the characters in b that are too small (those below the boundary).
• prefix_a + (len(b) - prefix_b) is the cost for condition 2: the mirror case.

We stop at index 24 (not 25) because a boundary after 'z' would require all characters in one string to be less than everything, which is impossible.

Visual walkthrough

Let's trace through the example with a = "aab" and b = "bcc". The frequency arrays are freq_a = [2, 1, 0, ...] and freq_b = [0, 1, 2, ...]. Watch how each condition gets evaluated and the minimum emerges.

Condition 1 with boundary 'b' gives cost 1: change a[2] from 'b' to 'a', so a becomes "aaa". Now every character in a ('a') is strictly less than every character in b ('b' and 'c'). That single change is the answer.

Complexity analysis

Time is O(n + m) where n and m are the lengths of strings a and b. Building the frequency arrays takes O(n + m). Evaluating all three conditions takes O(26) for condition 3 and O(25) for conditions 1 and 2, which is O(1). The total is dominated by the frequency counting step.

Space is O(1). The two frequency arrays each have a fixed size of 26. The prefix sum variables are just two integers. No additional data structures are needed.

The building blocks

1. Character frequency counting

The pattern of counting occurrences of each character in a string:

freq = [0] * 26
for ch in s:
    freq[ord(ch) - ord('a')] += 1

This gives you a complete picture of the string's character distribution in a single pass. You will use this same pattern in anagram problems, character rearrangement problems, and anywhere you need to compare the "shape" of two strings without caring about order.

2. Prefix sum over frequencies

The pattern of accumulating frequency counts to answer range queries:

prefix = 0
for c in range(25):
    prefix += freq[c]
    chars_below_boundary = prefix
    chars_at_or_above_boundary = total - prefix

After adding freq[c] to the running sum, prefix tells you how many characters have value <= c. The complement total - prefix tells you how many are strictly greater. This lets you evaluate "how many characters need to change to be below (or above) a given boundary" in O(1) per boundary, instead of re-scanning the string each time.

Edge cases

Before submitting, think through these scenarios:

• Single character strings: a = "a", b = "b". Every condition is already satisfied with 0 changes (condition 1 holds: 'a' is strictly less than 'b').
• Identical strings: a = "aaa", b = "aaa". Condition 3 is already satisfied with 0 changes.
• All same character but different: a = "aaa", b = "bbb". Condition 1 costs 0, condition 3 costs 3. Answer is 0.
• Strings of length 1: the minimum cost is at most 1 (change one character to match the other for condition 3, or to satisfy condition 1 or 2).
• Very long strings with uniform distribution: all 26 letters appear equally. Condition 3 is expensive, but conditions 1 and 2 might still be cheap depending on the overlap.
• One string is much longer than the other: the cost formulas still work because they account for len(a) and len(b) separately.

From understanding to recall

You have seen how a single pair of frequency arrays powers all three conditions, and how prefix sums turn what looks like an O(26n) scan into O(n + 26) total work. The logic is clean and the code is short. But reproducing it under pressure is a different challenge.

The details that trip people up are subtle. Do you loop range(26) or range(25) for the boundary conditions? Do you compute len(a) - prefix_a or prefix_a? Which term goes with which condition? These are not conceptual gaps. They are recall gaps, and spaced repetition is how you close them.

You practice writing the frequency counting, the condition 3 loop, and the prefix sum loop from memory at increasing intervals. After a few rounds, you see "minimum operations on two strings" in a problem description and the three-condition framework comes out automatically.

Related posts

• Group Anagrams - Another frequency counting pattern where character distributions determine group membership
• Find All Anagrams in a String - Sliding window over character frequencies, a close cousin of the counting approach here
• Minimum Number of Steps to Make Two Strings Anagram - Direct application of frequency difference counting between two strings

CodeBricks breaks Change Minimum Characters into its frequency counting and prefix sum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a string frequency problem shows up in your interview, you do not think about it. You just write it.