Solution: Change Minimum Characters to Satisfy One of Three Conditions

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #1737 (Medium): Change Minimum Characters to Satisfy One of Three Conditions

---

**Description: **

You are given two strings a and b that consist of lowercase letters. In one operation, you can change any character in a or b to any lowercase letter.

Your goal is to satisfy one of the following three conditions:

• Every letter in a is strictly less than every letter in b in the alphabet.
• Every letter in b is strictly less than every letter in a in the alphabet.
• Both a and b consist of only one distinct letter.

Return the minimum number of operations needed to achieve your goal.

---

Examples:

Example 1:
Input:	a = "aba", b = "caa"
Output:	2
Explanation:	Consider the best way to make each condition true: 1) Change b to "ccc" in 2 operations, then every letter in a is less than every letter in b. 2) Change a to "bbb" and b to "aaa" in 3 operations, then every letter in b is less than every letter in a. 3) Change a to "aaa" and b to "aaa" in 2 operations, then a and b consist of one distinct letter. The best way was done in 2 operations (either condition 1 or condition 3).

Example 2:
Input:	a = "dabadd", b = "cda"
Output:	3
Explanation:	The best way is to make condition 1 true by changing b to "eee".

---

Constraints:

• 1 <= a.length, b.length <= 10^5
• a and b consist only of lowercase letters.

---

Idea:

This problem is actually much more simple than it appears. Since we're going to dealing entirely with the counts of different characters, we will obviously need to create frequency maps (fmA, fmB) for both input strings (A, B).

We can check for the third condition by comparing the frequencies of any given character in both strings. The sum of those two frequencies (fmA[i] + fmB[i]) would be the number of characters we would not need to shift, so the best answer would be the total number of characters in both strings (lenA + lenB) minus the largest possible frequency sum.

For the first two conditions we can think logically about the distribution of the values in our frequency maps. Consider the example below:

   fmA =        [<------- C ------->|<--- D --->]
           a b c d e f g h i j k l m|n o p q r s t u v w x y z
   fmB =                [<--- E --->|<------- F ------->]

For any border between two characters (in this case "m" and "n"), we could make condition A > B by pushing all the characters in A before "n" (sum of range C) forward and also pushing all the characters in B after "m" (sum of range F) backward. Similarly, we could make condition B > A by pushing E forward and pushing D backward.

   conditionA = sumC + sumF
   conditionB = sumE + sumD

We also can figure out that sumC + sumD = lenA and sumE + sumF = lenB, so we can rewrite these as:

   conditionA = sumC + (lenB - sumE) = sumC - sumE + lenB
   conditionB = sumE + (lenA - sumC) = sumE - sumC + lenA

This allows us to iterate in one direction and keep a running sum of A and B up to that midpoint in order to check these possibilities. As we're checking the boundaries between characters, we only need to iterate through this check 25 times instead of 26.

Conveniently, conditionA and conditionB are also the inverse of each other, as they both sum up to lenA + lenB, so they can be used as either the number needing to change, or the number needing to stay the same.

   lenA + lenB - conditionA = conditionB
   lenA + lenB - conditionB = conditionA

That means we can use them with the same best from when we checked the third condition to find the maximum value of characters that don't need to be shifted in order to match one of the conditions.

Then we just need to find the difference between that number and the total number of characters, so we should return lenA + lenB - best.

---

Implementation:

In Javascript, we can use the much more efficient Uint32Array for our frequency maps by converting the characters to 0-indexed integers.

Python has the very convenient Counter() class, so we can make full use of that.

For Java and C++, the ability to convert characters to 0-indexed numbers simply by subtracting 'a' is very useful. But both languages only allow two arguments for max(), which requires nesting them to evaluate three values.

---

Javascript Code:

var minCharacters = function(A, B) {
    let lenA = A.length, fmA = new Uint32Array(26),
        lenB = B.length, fmB = new Uint32Array(26),
        best = sumA = sumB = 0
    for (let i = 0; i < lenA; i++) fmA[A.charCodeAt(i)-97]++
    for (let i = 0; i < lenB; i++) fmB[B.charCodeAt(i)-97]++
    for (let i = 0; i < 26; i++) best = Math.max(best, fmA[i]+fmB[i])
    for (let i = 0; i < 25; i++) {
        sumA += fmA[i], sumB += fmB[i]
        best = Math.max(best, sumA-sumB+lenB, sumB-sumA+lenA)
    }
    return lenA + lenB - best
};

---

Python Code:

class Solution:
    def minCharacters(self, A: str, B: str) -> int:
        lenA, lenB = len(A), len(B)
        fmA, fmB = Counter(A), Counter(B)
        best, sumA, sumB = 0, 0, 0
        for i in string.ascii_lowercase:
            best = max(best, fmA[i]+fmB[i])
        for i in string.ascii_lowercase[:-1]:
            sumA += fmA[i]
            sumB += fmB[i]
            best = max(best, sumA-sumB+lenB, sumB-sumA+lenA)
        return lenA + lenB - best

---

Java Code:

class Solution {
    public int minCharacters(String A, String B) {
        int lenA = A.length(), lenB = B.length();
        int[] fmA = new int[26], fmB = new int[26];
        int best = 0, sumA = 0, sumB = 0;
        for (char c: A.toCharArray()) fmA[c - 'a']++;
        for (char c: B.toCharArray()) fmB[c - 'a']++;
        for (int i = 0; i < 26; i++) best = Math.max(best, fmA[i]+fmB[i]);
        for (int i = 0; i < 25; i++) {
            sumA += fmA[i];
            sumB += fmB[i];
            best = Math.max(best, Math.max(sumA-sumB+lenB, sumB-sumA+lenA));
        }
        return lenA + lenB - best;
    }
}

---

C++ Code:

class Solution {
public:
    int minCharacters(string A, string B) {
        int lenA = A.size(), lenB = B.size();
        int fmA [26] = {}, fmB [26] = {};
        int best = 0, sumA = 0, sumB = 0;
        for (char c: A) fmA[c - 'a']++;
        for (char c: B) fmB[c - 'a']++;
        for (int i = 0; i < 26; i++) best = max(best, fmA[i]+fmB[i]);
        for (int i = 0; i < 25; i++) {
            sumA += fmA[i];
            sumB += fmB[i];
            best = max(best, max(sumA-sumB+lenB, sumB-sumA+lenA));
        }
        return lenA + lenB - best;
    }
};