LeetCode Solutions Blog

Change Minimum Characters to Satisfy One of Three Conditions

Number: 1859

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given two strings a and b consisting of lowercase letters, you can change any character in either string to any lowercase letter in one operation. The goal is to achieve at least one of the following conditions:

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

Return the minimum number of operations needed to reach one of these conditions.

Key Insights

Count the frequency of each character in both strings.
Use prefix sums over the alphabet (26 letters) to quickly determine how many changes are needed when forcing a string to only have characters up to a given letter, or starting from a letter.
For condition 1, try all partition boundaries (from 'a' to 'y') where a is forced to letters ≤ some letter and b is forced to letters > that letter.
For condition 2, reverse the roles compared to condition 1.
For condition 3, check for each letter the cost to convert both strings entirely to that letter.
Take the minimum operations among these three approaches.

Space and Time Complexity

Time Complexity: O(n + 26), essentially O(n) where n = |a| + |b| Space Complexity: O(1) extra space aside from input storage because frequency arrays and prefix sums use constant space (26 letters)

Solution

We first count the frequency of each lowercase letter in strings a and b. Then, build prefix sums for both such that:

For a given letter index i (0 for 'a', 25 for 'z'), prefix[i] in a represents the total count of letters ≤ that letter.
For condition 1, for each possible partition boundary (from 0 to 24), we force string a to only have letters ≤ i and string b to only have letters > i. The cost is the number of letters in a that are greater than i plus the number of letters in b that are ≤ i.
Similarly, for condition 2, we force string b to only have letters ≤ i and string a to only have letters > i.
For condition 3, for each letter, the cost is the entire length of a plus b minus its frequency, meaning convert every character in both strings to that letter.
Finally, return the minimum cost among these computed values.

We now provide code in multiple languages with detailed comments.

Code Solutions

# Python solution with detailed inline comments

def minCharacters(a: str, b: str) -> int:
    # Total lengths of the strings
    len_a, len_b = len(a), len(b)
    
    # Frequency arrays for each letter (26 for lowercase)
    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
    
    # Build prefix sums for a and for b:
    # prefix_a[i] : Total frequency of letters from 'a' (0) to letter represented by index i.
    prefix_a = [0] * 26
    prefix_b = [0] * 26
    prefix_a[0] = freq_a[0]
    prefix_b[0] = freq_b[0]
    for i in range(1, 26):
        prefix_a[i] = prefix_a[i - 1] + freq_a[i]
        prefix_b[i] = prefix_b[i - 1] + freq_b[i]
    
    # Initialize operations with a very high value.
    operations = float('inf')
    
    # Condition 3: Both strings become a single distinct letter.
    # For each letter, change all characters that are not this letter in both strings.
    for i in range(26):
        cost = (len_a - freq_a[i]) + (len_b - freq_b[i])
        operations = min(operations, cost)
    
    # Condition 1: Every letter in a < every letter in b.
    # We decide on a "boundary" index, letters in a must be <= boundary letter, b must be > boundary letter.
    for boundary in range(25):  # boundary from index 0 ('a') to index 24 ('y')
        # For a: letters that need to be changed are those > boundary.
        # For string a, characters <= boundary are already valid: prefix_a[boundary] available.
        change_a = len_a - prefix_a[boundary]
        # For b: letters that need to be changed are those <= boundary.
        change_b = prefix_b[boundary]
        operations = min(operations, change_a + change_b)
    
    # Condition 2: Every letter in b < every letter in a.
    # This is similar to condition 1, but swap roles for a and b.
    for boundary in range(25):  # boundary from index 0 to index 24
        change_b = len_b - prefix_b[boundary]
        change_a = prefix_a[boundary]
        operations = min(operations, change_a + change_b)
    
    return operations

# Example usage:
print(minCharacters("aba", "caa"))  # Expected output: 2