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 inb
in the alphabet.  Every letter in
b
is strictly less than every letter ina
in the alphabet.  Both
a
andb
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
andb
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 mn 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 0indexed 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 0indexed 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, sumAsumB+lenB, sumBsumA+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, sumAsumB+lenB, sumBsumA+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(sumAsumB+lenB, sumBsumA+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(sumAsumB+lenB, sumBsumA+lenA));
}
return lenA + lenB  best;
}
};
Top comments (0)