LeetCode 1737 - Change Minimum Characters to Satisfy One of Three Conditions

Difficulty: 🟡 Medium
Topics: Hash Table, String, Counting, Prefix Sum

Solution

Problem Understanding

The problem gives us two lowercase English strings, a and b. In a single operation, we may change any character in either string into any other lowercase English letter.

Our task is to determine the minimum number of character changes required so that at least one of the following conditions becomes true:

Every character in a is strictly smaller than every character in b.
Every character in b is strictly smaller than every character in a.
Both strings consist of only one distinct character.

The phrase "strictly smaller" refers to alphabetical order. For example, 'a' < 'b', 'b' < 'c', and so on. If condition 1 is satisfied, then the largest character in a must still be smaller than the smallest character in b.

The input sizes can each be as large as 10^5, which immediately tells us that expensive approaches involving repeated rescanning or checking all transformations explicitly will not work. We need something close to linear time.

Another important observation is that the alphabet size is fixed at only 26 lowercase letters. This strongly suggests that frequency counting and prefix sums will be useful, because we can efficiently reason about all possible character boundaries.

Some important edge cases include:

Strings that already satisfy one of the conditions.
Strings containing only one repeated letter.
Cases where both strings heavily overlap in character ranges.
Very small strings, such as length 1.
Cases where the optimal answer comes from condition 3 instead of conditions 1 or 2.

Because the alphabet size is constant, we can afford to evaluate all possible split points between letters efficiently.

Approaches

Brute Force Approach

A brute force solution would attempt every possible target transformation.

For conditions 1 and 2, we could try every possible boundary character. For example, suppose we choose 'd' as the dividing point for condition 1. Then every character in a must become one of 'a', 'b', or 'c', and every character in b must become 'd' or larger. We could count how many changes are needed for that boundary.

For condition 3, we could try every possible target letter from 'a' to 'z', converting all characters in both strings into that letter.

Even this simplified brute force already hints at a better direction. A truly naive implementation might repeatedly scan both strings for every boundary and every letter, leading to roughly:

26 possibilities for condition 3
25 split boundaries for condition 1
25 split boundaries for condition 2
Full scans of both strings each time

This gives a complexity of approximately O(26 * (n + m)), which is actually acceptable because the alphabet size is constant.

However, repeatedly rescanning strings is unnecessary. We can optimize further using frequency arrays and prefix sums.

Key Insight

The critical observation is that there are only 26 lowercase letters.

Instead of repeatedly scanning the strings, we can:

Count how many times each character appears in a and b.
Build prefix sums to quickly determine:

How many characters are less than a boundary
How many characters are greater than or equal to a boundary

This allows us to evaluate each condition in constant time per boundary.

For condition 3, we simply choose a target character and keep all occurrences already matching that character.

For conditions 1 and 2, we test every split between letters:

If the split is after 'c', then:
a must contain only 'a' to 'c'
b must contain only 'd' to 'z'

Using prefix sums makes these counts extremely efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(26 × (n + m))	O(1)	Repeatedly scans strings for every boundary
Optimal	O(n + m + 26)	O(26)	Uses frequency counting and prefix sums

Algorithm Walkthrough

Create two frequency arrays of size 26.

Each index corresponds to a lowercase letter:

Index 0 represents 'a'
Index 1 represents 'b'
...
Index 25 represents 'z'

We count how many times each letter appears in a and b. 2. Compute the answer for condition 3.

We try making both strings consist of only one distinct character.

For every letter:

Keep all occurrences already equal to that letter
Change every other character

If:

countA[i] is the number of occurrences in a
countB[i] is the number of occurrences in b

then the operations needed are:

len(a) + len(b) - countA[i] - countB[i]

We take the minimum over all 26 letters. 3. Build prefix sums for both frequency arrays.

The prefix sum at index i tells us how many characters are less than or equal to letter i.

This lets us quickly answer range count queries. 4. Evaluate condition 1.

We try every split between adjacent letters.

Suppose the split is after letter i.

Then:

a may only contain letters 0..i
b may only contain letters i+1..25

The required changes are:

Characters in a greater than i
Characters in b less than or equal to i

Evaluate condition 2.

This is symmetric to condition 1.

For the same split:

b may only contain letters 0..i
a may only contain letters i+1..25

Return the minimum value among all possibilities.

Why it works

The algorithm works because every valid configuration for conditions 1 and 2 can be represented by a boundary between two adjacent letters. Since the alphabet contains only 26 letters, testing all 25 boundaries guarantees that we examine every possible ordering arrangement.

For condition 3, any valid final state must consist entirely of one repeated character, so checking all 26 target letters guarantees we find the optimal one.

Because the algorithm exhaustively evaluates all valid structural possibilities while using exact frequency counts, the minimum computed value is guaranteed to be optimal.

Python Solution

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        count_a = [0] * 26
        count_b = [0] * 26

        for ch in a:
            count_a[ord(ch) - ord('a')] += 1

        for ch in b:
            count_b[ord(ch) - ord('a')] += 1

        n = len(a)
        m = len(b)

        answer = n + m

        # Condition 3:
        # Both strings consist of only one distinct letter
        for i in range(26):
            changes = (n - count_a[i]) + (m - count_b[i])
            answer = min(answer, changes)

        prefix_a = count_a[:]
        prefix_b = count_b[:]

        for i in range(1, 26):
            prefix_a[i] += prefix_a[i - 1]
            prefix_b[i] += prefix_b[i - 1]

        # Conditions 1 and 2
        for i in range(25):
            # Condition 1:
            # all chars in a < all chars in b
            changes_a = n - prefix_a[i]
            changes_b = prefix_b[i]
            answer = min(answer, changes_a + changes_b)

            # Condition 2:
            # all chars in b < all chars in a
            changes_b = m - prefix_b[i]
            changes_a = prefix_a[i]
            answer = min(answer, changes_a + changes_b)

        return answer

The implementation begins by building two frequency arrays, one for each string. This gives us constant time access to how many times each character appears.

Next, the code evaluates condition 3. For every possible target letter, we count how many characters already match that letter and how many must be changed.

After that, prefix sums are constructed. These prefix arrays allow us to quickly determine:

How many characters are less than or equal to a given letter
How many characters are greater than a given letter

The final loop iterates over all 25 possible boundaries between letters. For each boundary, the code computes the number of changes required for both ordering conditions and updates the global minimum.

The solution is efficient because every calculation after preprocessing is constant time.

Go Solution

func minCharacters(a string, b string) int {
	countA := make([]int, 26)
	countB := make([]int, 26)

	for _, ch := range a {
		countA[ch-'a']++
	}

	for _, ch := range b {
		countB[ch-'a']++
	}

	n := len(a)
	m := len(b)

	answer := n + m

	// Condition 3
	for i := 0; i < 26; i++ {
		changes := (n - countA[i]) + (m - countB[i])
		if changes < answer {
			answer = changes
		}
	}

	prefixA := make([]int, 26)
	prefixB := make([]int, 26)

	copy(prefixA, countA)
	copy(prefixB, countB)

	for i := 1; i < 26; i++ {
		prefixA[i] += prefixA[i-1]
		prefixB[i] += prefixB[i-1]
	}

	// Conditions 1 and 2
	for i := 0; i < 25; i++ {
		// Condition 1
		changesA := n - prefixA[i]
		changesB := prefixB[i]

		if changesA+changesB < answer {
			answer = changesA + changesB
		}

		// Condition 2
		changesB = m - prefixB[i]
		changesA = prefixA[i]

		if changesA+changesB < answer {
			answer = changesA + changesB
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version. Since Go does not have built in dynamic lists like Python, fixed size slices are used for the frequency and prefix arrays.

Character indexing is performed using rune arithmetic:

countA[ch-'a']++

This converts each lowercase letter into an index from 0 to 25.

No special handling for empty strings is needed because the constraints guarantee both strings contain at least one character.

Worked Examples

Example 1

a = "aba"
b = "caa"

Step 1: Frequency Counts

Letter	a Count	b Count
a	2	2
b	1	0
c	0	1

All other letters have frequency 0.

Step 2: Condition 3

Try making both strings one letter.

Target Letter	Changes Needed
a	1
b	5
c	5

For target 'a':

a needs 1 change (b -> a)
b needs 1 change (c -> a)

Total = 2

Current answer = 2.

Step 3: Prefix Sums

Letter	Prefix A	Prefix B
a	2	2
b	3	2
c	3	3

Step 4: Check Boundaries

Split after 'b':

Condition 1:

a must stay <= 'b'
b must become > 'b'

Changes:

a: 0
b: 2

Total = 2

This matches the best answer.

Final answer = 2.

Example 2

a = "dabadd"
b = "cda"

Step 1: Frequency Counts

Letter	a Count	b Count
a	2	1
b	1	0
c	0	1
d	3	1

Step 2: Evaluate Boundary After `'d'`

Condition 1:

a must be <= 'd'
b must be > 'd'

All characters in a already satisfy the condition.

Characters in b:

c, d, a

All must become larger than 'd'.

Required changes = 3.

This becomes the minimum answer.

Final answer = 3.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m + 26)	Counting characters and checking all boundaries
Space	O(26)	Fixed size frequency and prefix arrays

The dominant cost comes from scanning the two input strings once. Every other operation works over the fixed alphabet size of 26, which is constant. Therefore the runtime is effectively linear in the input size.

The space usage is constant because the algorithm only stores several arrays of length 26 regardless of input size.

Test Cases

solution = Solution()

assert solution.minCharacters("aba", "caa") == 2  # provided example 1
assert solution.minCharacters("dabadd", "cda") == 3  # provided example 2

assert solution.minCharacters("a", "a") == 0  # already satisfies condition 3
assert solution.minCharacters("a", "z") == 0  # already satisfies condition 1
assert solution.minCharacters("z", "a") == 0  # already satisfies condition 2

assert solution.minCharacters("abc", "abc") == 3  # overlapping ranges
assert solution.minCharacters("aaa", "aaa") == 0  # already one distinct letter
assert solution.minCharacters("abc", "def") == 0  # already ordered

assert solution.minCharacters("zzz", "zzz") == 0  # same repeated character
assert solution.minCharacters("abcde", "fghij") == 0  # perfect separation
assert solution.minCharacters("bbbb", "aaaa") == 0  # already satisfies condition 2

assert solution.minCharacters("az", "za") == 2  # requires multiple changes
assert solution.minCharacters("leetcode", "codeleet") >= 0  # stress style mixed letters

assert solution.minCharacters("a" * 100000, "z" * 100000) == 0  # maximum size style case

Test Summary

Test	Why
`"aba", "caa"`	Validates provided example
`"dabadd", "cda"`	Validates provided example
`"a", "a"`	Smallest possible equal strings
`"a", "z"`	Already satisfies condition 1
`"z", "a"`	Already satisfies condition 2
`"abc", "abc"`	Overlapping character ranges
`"aaa", "aaa"`	Already satisfies condition 3
`"abc", "def"`	Perfect alphabetical separation
`"zzz", "zzz"`	Single repeated high letter
`"bbbb", "aaaa"`	Reverse ordering condition
`"az", "za"`	Requires careful boundary handling
Large repeated strings	Stress test for performance

Edge Cases

One important edge case occurs when the strings already satisfy one of the conditions. For example, a = "abc" and b = "xyz" already satisfy condition 1 because every character in a is smaller than every character in b. A buggy implementation might still perform unnecessary changes. This implementation correctly returns 0 because the boundary checks naturally produce zero required modifications.

Another tricky edge case is when both strings contain only one repeated character, such as a = "aaaa" and b = "aaaa". In this situation, condition 3 is already satisfied. The implementation handles this efficiently because the frequency counting immediately shows that all characters already match the target letter.

A third important edge case involves boundaries near the ends of the alphabet. For example, if the split occurs after 'y', then all characters in one string must be 'z'. Implementations with incorrect prefix handling often make off by one mistakes here. This solution avoids that problem by carefully interpreting the split as:

left side uses letters 0..i
right side uses letters i+1..25

and iterating only through valid boundaries from 0 to 24.

Another subtle case is very small strings of length 1. Since a single character trivially forms a uniform string, condition 3 is always easy to satisfy. The implementation works correctly because the frequency arrays and prefix sums naturally support strings of any valid size.

LeetCode 1737 - Change Minimum Characters to Satisfy One of Three Conditions

Solution

Problem Understanding

Approaches

Brute Force Approach

Key Insight

Approach Comparison

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Step 1: Frequency Counts

Step 2: Condition 3

Step 3: Prefix Sums

Step 4: Check Boundaries

Example 2

Step 1: Frequency Counts

Step 2: Evaluate Boundary After 'd'

Complexity Analysis

Test Cases

Test Summary

Edge Cases

Step 2: Evaluate Boundary After `'d'`