<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:
    def minCharacters(self, a: str, b: str) -> int:
        """
        Main idea: we have subroutines for each condition, and then return the minimum number of operations
        it takes to satisfy each condition. 

        Function that tells us a < b  is 10 ops
        b < a is 1 op
        a and b only 1 distinct is 2 ops

        we choose b < a.
        """
        """
        returns the number of steps to satisfy the condition that every character in s1 
        is strictly less than every character in s2

        Since we're dealing with the alphabet, we don't need to worry much about time complexity,
        because the alphabet contains a constant 26 letters.
        Let's assemble a frequency list for the number of letters of each string
        """

        # Vacuously true
        if not b:
            return 0

        def freq_arr(s1: str) -> Tuple[List[int], str]:
            s1_most_freq_c, s1_most_freq = 0, 0
            s1_freq = [0] * 26
            for c in s1:
                char_index = ord(c) - 97
                s1_freq[char_index] += 1 
                if s1_freq[char_index] > s1_most_freq:
                    s1_most_freq = s1_freq[char_index]
                    s1_most_freq_c = char_index
            return s1_freq, s1_most_freq_c
        
        a_freq, a_most_freq = freq_arr(a)
        b_freq, b_most_freq = freq_arr(b)

        condition_3_ops = (len(a)-a_freq[a_most_freq]) + (len(b)-b_freq[b_most_freq])
        
        def ops_to_make_less_than(freq1: List[int], freq2: List[int]) -> int:
            # base case: freq1 < freq2: return 0
            max_non_zero_freq_1 = max([i for i in range(len(freq1)) if freq1[i] > 0])
            min_non_zero_freq_2 = min([i for i in range(len(freq2)) if freq2[i] > 0])                
            
            dp = {}
            """
            Precondition: i is the location of the maximum non-zero letter in freq1,
            j is the location of the minimum non-zero thing in freq 2
            """
            def best_ops(i: int, j: int):
                # We've seen this case
                if (i, j) in dp:
                    return dp[(i, j)]
                # freq1 < freq2
                if i < j:
                    return 0
                
                next_largest1 = i-1
                while next_largest1 >= 0 and freq1[next_largest1] == 0:
                    next_largest1 -= 1
                
                next_smallest_2 = j+1
                while next_smallest_2 <= 25 and freq2[next_smallest_2] == 0:
                    next_smallest_2 += 1
                
                dp[(i, j)] = min(freq1[i] + best_ops(next_largest1, j), freq2[j] + best_ops(i, next_smallest_2))
                return dp[(i, j)]
            
            required_changes = 0
            if max_non_zero_freq_1 == 25:
                required_changes += freq1[max_non_zero_freq_1]
                max_non_zero_freq_1 -= 1
                while max_non_zero_freq_1 >= 0 and freq1[max_non_zero_freq_1] == 0:
                    max_non_zero_freq_1 -= 1
            
            if min_non_zero_freq_2 == 0:
                required_changes += freq2[min_non_zero_freq_2]
                min_non_zero_freq_2 += 1
                while min_non_zero_freq_2 <= 25 and freq2[min_non_zero_freq_2] == 0:
                    min_non_zero_freq_2 += 1

            return required_changes + best_ops(max_non_zero_freq_1, min_non_zero_freq_2)

        condition_1_ops = ops_to_make_less_than(a_freq, b_freq)
        condition_2_ops = ops_to_make_less_than(b_freq, a_freq)
        print(f"condition1 = {condition_1_ops} ")
        print(f"condition2 = {condition_2_ops} ")
        print(f" condition3 = {condition_3_ops} ")
        
        
        

        return min(condition_1_ops,condition_2_ops,condition_3_ops)
17800