Krammer's blog

https://leetcode.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/ from Google

Thinking process:

Basically no good idea for this, but since a and b consist only lowercase letters, we can just solve this with a brute force approach.

So the idea is very simple. For the first condition: Every letter in a is strictly less than every letter in b in the alphabet, we can set a boundary that given a letter x, every letter in a is smaller than x, and every letter in b is equal to or greater than x. This can be easily checked by iterating through a and b once.

Same thing can be applied to condition 2 and 3. To check all the boundary, we just need to check from a to z, which takes O(26*N) time.

Here is the code.

 1class Solution {
 2public:
 3    int minCharacters(string a, string b) {
 4        int ans = a.size() + b.size();
 5        for (char t='b'; t<='z'; t++) {
 6            int cur = 0;
 7            for (auto c : a) if (c >= t) cur++;
 8            for (auto c : b) if (c < t) cur++;
 9            ans = min(ans, cur);
10        }
11        for (char t='b'; t<='z'; t++) {
12            int cur = 0;
13            for (auto c : a) if (c < t) cur++;
14            for (auto c : b) if (c >= t) cur++;
15            ans = min(ans, cur);
16        }
17        for (char t='a'; t<='z'; t++) {
18            int cur = 0;
19            for (auto c : a) if (c != t) cur++;
20            for (auto c : b) if (c != t) cur++;
21            ans = min(ans, cur);
22        }
23        return ans;
24    }
25};

Editorial: LeetCode 1737 Change Minimum Characters to Satisfy One of Three Conditions