Problem Description

You are given two strings, a and b, both consisting only of lowercase English letters. Your task is to determine the minimum number of characters you need to change in either string (or both) so that at least one of the following three conditions is satisfied:

• Every character in a is strictly less than every character in b in alphabetical order.
• Every character in b is strictly less than every character in a in alphabetical order.
• Both a and b consist of only one distinct letter (but not necessarily the same letter for both).

You may change any character in either string to any lowercase English letter. Your goal is to minimize the total number of changes needed to satisfy at least one of the conditions above. Each character change counts as one operation.

Thought Process

The problem asks us to make minimal changes to two strings so that one of three conditions is satisfied. At first glance, brute-forcing all possible letter changes sounds possible, but with 26 letters and strings of up to 10⁵ in length, that's not feasible.

Instead, let's break down the three conditions:

• For the first two conditions, we need all characters in one string to be strictly less than all characters in the other. This suggests picking a "dividing letter" and changing all letters in a to be less than it and all in b to be at least it (or vice versa).
• The third condition is simpler: make all letters in a the same, and all in b the same (possibly different from a). We can count the most common letter in each string and change the rest.

The key idea is to use frequency counting and prefix sums to efficiently compute, for each possible dividing letter, the number of changes needed for conditions 1 and 2.

Solution Approach

Let's walk through the solution step-by-step:

1. Count Frequencies:
   • Count how many times each letter appears in a and b. Store these in arrays of size 26 (for each lowercase letter).
2. Prefix Sums:
   • Compute prefix sums of the frequency arrays. This allows us to quickly find, for any letter c, how many letters in a (or b) are less than or equal to c.
3. Condition 3 (Single Letter in Each String):
   • For a, the minimum number of changes is len(a) - max frequency in a. Similarly for b.
   • Try all 26 letters for a and all 26 for b, and pick the pair with the minimum total changes.
4. Conditions 1 and 2 (Strictly Less):
   • For every possible dividing letter c from 'a'+1 to 'z', calculate:
   • To make every letter in a < c and every letter in b ≥ c (Condition 1):
   • Change all letters in a that are ≥ c (i.e., len(a) - prefixA[c-1]), and all in b that are < c (prefixB[c-1]).
   • Similarly, swap roles for Condition 2.
   • Try all possible dividing letters and keep the minimum changes found.
5. Return the Minimum:
   • The answer is the minimum number of changes among all three conditions.

This approach is efficient, using only O(N) time for counting and O(1) for each of the 26 letters.

Example Walkthrough

Let's use a = "aba" and b = "caa" as an example.

1. Frequencies:
   • a: 'a' = 2, 'b' = 1
   • b: 'a' = 2, 'c' = 1
2. Condition 3:
   • Make all letters in a the same: minimum changes = 1 (change 'b' to 'a')
   • Make all letters in b the same: minimum changes = 1 (change 'c' to 'a')
   • Total = 2
3. Condition 1:
   • Try dividing after 'a' (i.e., all in a < 'b', all in b ≥ 'b')
   • In a, 'b' is not < 'b', so 1 change (change 'b' to 'a')
   • In b, both 'a's are not ≥ 'b', so 2 changes (change both 'a's to 'b' or 'c')
   • Total = 3
   • Try dividing after 'b' (all in a < 'c', all in b ≥ 'c')
   • In a, all are < 'c', so 0 changes
   • In b, 'a's are not ≥ 'c', so 2 changes
   • Total = 2
4. Condition 2:
   • Try dividing after 'b' (all in b < 'c', all in a ≥ 'c')
   • In b, all are < 'c', so 0 changes
   • In a, none are ≥ 'c', so 3 changes
   • Total = 3
5. Minimum:
   • The minimum among all is 2.

Thus, the answer is 2.

Code Implementation

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        countA = [0] * 26
        countB = [0] * 26
        for c in a:
            countA[ord(c) - ord('a')] += 1
        for c in b:
            countB[ord(c) - ord('a')] += 1

        # Condition 3: make all letters in each string the same
        res = len(a) + len(b)
        for i in range(26):
            res = min(res, len(a) - countA[i] + len(b) - countB[i])

        # Prefix sums for conditions 1 and 2
        preA = [0] * 26
        preB = [0] * 26
        preA[0] = countA[0]
        preB[0] = countB[0]
        for i in range(1, 26):
            preA[i] = preA[i-1] + countA[i]
            preB[i] = preB[i-1] + countB[i]

        for i in range(1, 26):  # dividing letter (from 'b' to 'z')
            # a: letters < i, b: letters >= i
            changeA = len(a) - preA[i-1]
            changeB = preB[i-1]
            res = min(res, changeA + changeB)
            # b: letters < i, a: letters >= i
            changeB = len(b) - preB[i-1]
            changeA = preA[i-1]
            res = min(res, changeA + changeB)
        return res
      

class Solution {
public:
    int minCharacters(string a, string b) {
        vector<int> countA(26, 0), countB(26, 0);
        for (char c : a) countA[c - 'a']++;
        for (char c : b) countB[c - 'a']++;

        int res = a.size() + b.size();
        // Condition 3
        for (int i = 0; i < 26; ++i) {
            res = min(res, (int)a.size() - countA[i] + (int)b.size() - countB[i]);
        }

        // Prefix sums
        vector<int> preA(26, 0), preB(26, 0);
        preA[0] = countA[0];
        preB[0] = countB[0];
        for (int i = 1; i < 26; ++i) {
            preA[i] = preA[i-1] + countA[i];
            preB[i] = preB[i-1] + countB[i];
        }

        for (int i = 1; i < 26; ++i) {
            // a: letters < i, b: letters >= i
            int changeA = (int)a.size() - preA[i-1];
            int changeB = preB[i-1];
            res = min(res, changeA + changeB);

            // b: letters < i, a: letters >= i
            changeB = (int)b.size() - preB[i-1];
            changeA = preA[i-1];
            res = min(res, changeA + changeB);
        }
        return res;
    }
};
      

class Solution {
    public int minCharacters(String a, String b) {
        int[] countA = new int[26];
        int[] countB = new int[26];
        for (char c : a.toCharArray()) countA[c - 'a']++;
        for (char c : b.toCharArray()) countB[c - 'a']++;

        int res = a.length() + b.length();
        // Condition 3
        for (int i = 0; i < 26; ++i) {
            res = Math.min(res, a.length() - countA[i] + b.length() - countB[i]);
        }

        // Prefix sums
        int[] preA = new int[26];
        int[] preB = new int[26];
        preA[0] = countA[0];
        preB[0] = countB[0];
        for (int i = 1; i < 26; ++i) {
            preA[i] = preA[i-1] + countA[i];
            preB[i] = preB[i-1] + countB[i];
        }

        for (int i = 1; i < 26; ++i) {
            // a: letters < i, b: letters >= i
            int changeA = a.length() - preA[i-1];
            int changeB = preB[i-1];
            res = Math.min(res, changeA + changeB);

            // b: letters < i, a: letters >= i
            changeB = b.length() - preB[i-1];
            changeA = preA[i-1];
            res = Math.min(res, changeA + changeB);
        }
        return res;
    }
}
      

var minCharacters = function(a, b) {
    let countA = new Array(26).fill(0), countB = new Array(26).fill(0);
    for (let c of a) countA[c.charCodeAt(0) - 97]++;
    for (let c of b) countB[c.charCodeAt(0) - 97]++;

    let res = a.length + b.length;
    // Condition 3
    for (let i = 0; i < 26; ++i) {
        res = Math.min(res, a.length - countA[i] + b.length - countB[i]);
    }

    // Prefix sums
    let preA = new Array(26).fill(0), preB = new Array(26).fill(0);
    preA[0] = countA[0];
    preB[0] = countB[0];
    for (let i = 1; i < 26; ++i) {
        preA[i] = preA[i-1] + countA[i];
        preB[i] = preB[i-1] + countB[i];
    }

    for (let i = 1; i < 26; ++i) {
        // a: letters < i, b: letters >= i
        let changeA = a.length - preA[i-1];
        let changeB = preB[i-1];
        res = Math.min(res, changeA + changeB);

        // b: letters < i, a: letters >= i
        changeB = b.length - preB[i-1];
        changeA = preA[i-1];
        res = Math.min(res, changeA + changeB);
    }
    return res;
};
      

Time and Space Complexity

• Brute-force approach:
  • Would involve trying all possible ways to change each character in both strings, leading to exponential time complexity (O(26ⁿ)). This is infeasible for large strings.
• Optimized approach (as above):
  • Counting frequencies: O(n + m), where n and m are the lengths of a and b.
  • Prefix sums: O(26).
  • Trying all dividing letters: O(26).
  • Overall time complexity: O(n + m).
  • Space complexity: O(1) (since the frequency arrays are always of size 26, regardless of input size).

Summary

To solve the "Change Minimum Characters to Satisfy One of Three Conditions" problem, we use frequency counting and prefix sums to efficiently check, for each letter, the minimum number of changes needed for each condition. By leveraging the small alphabet size, we avoid brute-force and can handle large inputs efficiently. The key insight is to reduce the problem to operations on letter frequencies and to systematically try all possible dividing points for the first two conditions, ensuring an optimal and elegant solution.