<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>

const int M = 26;

class Solution {
public:
    
    // max(a) < min(b)
    int condition1(vector<int>& a, vector<int>& b) {
        int ans = INT_MAX;
        for(int i=1; i<M; i++) {
            // let ith be the minimum character of b
            
            int cost = 0;
            // let's ensure every character in b >= i
            for(int j=0; j<M; j++) {
                if(j<i) {
                    // bring these upto i
                    cost += b[j];
                }
                // if j>=i, we can ignore those
            }
            
            // let's ensure every character in a < i
            for(int j=0; j<M; j++) {
                if(j>=i) {
                    // bring these upto i-1
                    cost += a[j];
                }
            }
            
            ans = min(ans, cost);
        }
        
        return ans;
    }
    
    int condition3(vector<int>& a, vector<int>& b) {
        int ans = INT_MAX;
        
        for(int i=0; i<M; i++) {
            int cost = 0;
            for(int j=0; j<M; j++) {
                if(i == j) {
                    continue;
                }
                cost += a[j];
                cost += b[j];
            }
            ans = min(ans, cost);
        }
        
        return ans;
    }
    
    int minCharacters(string a, string b) {
        vector<int> sa(M, 0), sb(M, 0);
        
        int m = a.length(), n = b.length();
        
        for(int i=0; i<m; i++) {
            sa[a[i]-'a']++;
        }
        
        for(int i=0; i<n; i++) {
            sb[b[i]-'a']++;
        }
        
        int c1 = condition1(sa, sb);
        int c2 = condition1(sb, sa);
        int c3 = condition3(sa, sb);
        
        // cout<<c1<<" "<<c2<<" "<<c3<<endl;
        
        return min({c1, c2, c3});
    }
};
16400