Solution: Change Minimum Characters to Satisfy One of Three Conditions
Tags: algorithms, javascript, java, python
Published: 2021-02-07 07:54:48

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/discuss/1032693).*

---

####[Leetcode Problem #1737 (*Medium*): Change Minimum Characters to Satisfy One of Three Conditions](https://leetcode.com/problems/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:<br><br>1) Change b to "ccc" in 2 operations, then every letter in a is less than every letter in b.<br>2) Change a to "bbb" and b to "aaa" in 3 operations, then every letter in b is less than every letter in a.<br>3) Change a to "aaa" and b to "aaa" in 2 operations, then a and b consist of one distinct letter.<br><br>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:
```javascript
   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.
```javascript
   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:
```javascript
   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.
```javascript
   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:***
```javascript
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:***
```python
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:***
```java
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:***
```c++
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;
    }
};
```