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

<p>Your goal is to satisfy <strong>one</strong> of the following three conditions:</p>

<ul>
	<li><strong>Every</strong> letter in <code>a</code> is <strong>strictly less</strong> than <strong>every</strong> letter in <code>b</code> in the alphabet.</li>
	<li><strong>Every</strong> letter in <code>b</code> is <strong>strictly less</strong> than <strong>every</strong> letter in <code>a</code> in the alphabet.</li>
	<li><strong>Both</strong> <code>a</code> and <code>b</code> consist of <strong>only one</strong> distinct letter.</li>
</ul>

<p>Return <em>the <strong>minimum</strong> number of operations needed to achieve your goal.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> a = &quot;aba&quot;, b = &quot;caa&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> Consider the best way to make each condition true:
1) Change b to &quot;ccc&quot; in 2 operations, then every letter in a is less than every letter in b.
2) Change a to &quot;bbb&quot; and b to &quot;aaa&quot; in 3 operations, then every letter in b is less than every letter in a.
3) Change a to &quot;aaa&quot; and b to &quot;aaa&quot; 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).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> a = &quot;dabadd&quot;, b = &quot;cda&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> The best way is to make condition 1 true by changing b to &quot;eee&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= a.length, b.length &lt;= 10<sup>5</sup></code></li>
	<li><code>a</code> and <code>b</code> consist only of lowercase letters.</li>
</ul>

// Idea: prefix sum / suffix sum, or try using each letter as the boundary.
class Solution {
    static tuple<unordered_map<char, int>, char, char, int>
    analyze(const string& s) {
        unordered_map<char, int> fm;
        char minChar = s[0];
        char maxChar = s[0];
        int maxFreq = 0;
        for (char c : s) {
            ++fm[c];
            maxFreq = max(maxFreq, fm[c]);
            minChar = min(minChar, c);
            maxChar = max(maxChar, c);
        }
        return {std::move(fm), minChar, maxChar, maxFreq};
    }

    static int costOfGoal1(char bMinChar, char bMaxChar,
                           const unordered_map<char, int>& fma) {
        // make chars in `a` less than bMinChar
        int cost1 = 0;
        if (bMinChar == 'a') {
            cost1 = INT_MAX; // not possible
        } else {             // decrease big letters in `a` to (bMinChar-1)
            for (auto [c, f] : fma) {
                if (c >= bMinChar) {
                    cost1 += f;
                }
            }
        }
        // make chars in `a` greater than bMaxChar
        int cost2 = 0;
        if (bMaxChar == 'z') {
            cost2 = INT_MAX; // not possible
        } else {
            // decrease small chars in `a`
            for (auto [c, f] : fma) {
                if (c <= bMaxChar) {
                    cost2 += f;
                }
            }
        }
        // cout << "costOfGoal1(): make less: " << cost1
        //      << "; make greater: " << cost2 << endl;
        return min(cost1, cost2);
    }

    // O(L^2), where L = 26 the size of the alphabet.
    // this can be improved to O(L) = O(26) if we use prefix-sum and suffix-sum
    static int useEachLetterAsBoundary(const unordered_map<char, int>& fma,
                                       const unordered_map<char, int>& fmb) {
        int best = INT_MAX;
        for (char div = 'b'; div <= 'z'; ++div) {
            // let a's chars be < div,
            int cost1 = 0;
            int cost2 = 0;
            for (auto [c, f] : fma) {
                if (c >= div) {
                    cost1 += f;
                } else {
                    cost2 += f;
                }
            }
            // let b's chars be >= div
            for (auto [c, f] : fmb) {
                if (c < div) {
                    cost1 += f;
                } else {
                    cost2 += f;
                }
            }
            best = min(best, min(cost1, cost2));
        }
        return best;
    }

public:
    int minCharacters(string a, string b) {
        unordered_map<char, int> fma, fmb;
        char aMinChar, bMinChar, aMaxChar, bMaxChar;
        int aMaxFreq, bMaxFreq;
        tie(fma, aMinChar, aMaxChar, aMaxFreq) = analyze(a);
        tie(fmb, bMinChar, bMaxChar, bMaxFreq) = analyze(b);
        // goal 3: Both a and b consist of only one distinct letter.
        int cost3 = (a.size() - aMaxFreq) + b.size() - bMaxFreq;

        // goal 1: Every letter in `a` is strictly less than every letter in b
        // in the alphabet.
        // int cost1 = costOfGoal1(bMinChar, bMaxChar, fma);
        // int cost2 = costOfGoal1(aMinChar, aMaxChar, fmb);

        int cost4 = useEachLetterAsBoundary(fma, fmb);
        // cout << "cost3: " << cost3 << ", cost1: " << cost1
        //      << ", cost2: " << cost2 << ", cost4: " << cost4 << endl;
        // return min(min(cost3, cost4), min(cost1, cost2));
        return min(cost3, cost4);
    }
};
17600