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

class Solution {
public:
    int minCharacters(string a, string b) {
        
        int m = a.size(), n = b.size(), res = m + n;
        vector<int> c1(26), c2(26);
        for (char& c: a)
            c1[c - 'a']++;
        for (char& c: b)
            c2[c - 'a']++;

        for (int i = 0; i < 26; ++i) {
            res = min(res, m + n - c1[i] - c2[i]); // condition 3
            if (i > 0) {
                c1[i] += c1[i - 1]; // cumulative freq of char i and smaller chars b4 char i
                c2[i] += c2[i - 1];
                // so m - c1[i] will be freq of char after i
            }
            if (i < 25) {
                res = min(res, m - c1[i] + c2[i]); // condition 1
                res = min(res, n - c2[i] + c1[i]); // condition 2
            }
        }
        return res;
    }
};

// For those who still wondering why

// To meet condition 1,
// which is a < b,
// we need (m - c1[i]) + c2[i]
// we did that because, if we want to convert a smaller than b, at the ith iteration, the element in the c1 after the i will be required to be changed to smaller letter, no of such letters will -> total no of element - total no of elements before the ith and hence m - c1[i], also we need to change the letters in C2 which are smaller than ith in C1, and the no of such elements will be C2[i], hence we did + c2[i]

// Honestly you can take time to understand this, it took me 10 mins to figure this out xD

// Explanation
// Count the frequcy of each character in a and b.
// Find the most common characters most_common = max((c1 + c2).values()),
// this help meet the condition 3 with m + n - most_common.

// Then we calculate the accumulate prefix sum of count.
// This help finding the number of smaller characters in O(1) time.

// Enumerate the character i a,b,c...x,y,
// To meet condition 1,
// which is a < b,
// we need (m - c1[i]) + c2[i]

// To meet condition 2,
// which is a > b,
// we need n - c2[i] + c1[i]


// Complexity
// Time O(m + n)
// Space O(26)





16100