<p>The <strong>variance</strong> of a string is defined as the largest difference between the number of occurrences of <strong>any</strong> <code>2</code> characters present in the string. Note the two characters may or may not be the same.</p>

<p>Given a string <code>s</code> consisting of lowercase English letters only, return <em>the <strong>largest variance</strong> possible among all <strong>substrings</strong> of</em> <code>s</code>.</p>

<p>A <strong>substring</strong> is a contiguous sequence of characters within a string.</p>

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

<pre>
<strong>Input:</strong> s = &quot;aababbb&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong>
All possible variances along with their respective substrings are listed below:
- Variance 0 for substrings &quot;a&quot;, &quot;aa&quot;, &quot;ab&quot;, &quot;abab&quot;, &quot;aababb&quot;, &quot;ba&quot;, &quot;b&quot;, &quot;bb&quot;, and &quot;bbb&quot;.
- Variance 1 for substrings &quot;aab&quot;, &quot;aba&quot;, &quot;abb&quot;, &quot;aabab&quot;, &quot;ababb&quot;, &quot;aababbb&quot;, and &quot;bab&quot;.
- Variance 2 for substrings &quot;aaba&quot;, &quot;ababbb&quot;, &quot;abbb&quot;, and &quot;babb&quot;.
- Variance 3 for substring &quot;babbb&quot;.
Since the largest possible variance is 3, we return it.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;abcde&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong>
No letter occurs more than once in s, so the variance of every substring is 0.
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution:
    def largestVariance(self, s: str) -> int:
        """
        import itertools
        import collections

        s = 'aabbacaa'
        counter = collections.Counter(s)
        # Counter({'a': 5, 'b': 2})
        list(itertools.permutations(counter, 2))
        # [('a', 'b'), ('b', 'a')]
        """
        counter = collections.Counter(s)
        result = 0
        
        for char1, char2 in itertools.permutations(counter, 2):
            difference = 0

            char1_count = counter[char1]
            char2_count = counter[char2]
            seen_char1 = False
            seen_char2 = False

            for current in s:
                # if the current char is neither char 1 or 2, continue, because there is nothing to compare
                if current not in (char1, char2):
                    continue
                if difference < 0:
                    if not char1_count:
                        # this breaks out of the nested for only,
                        # its because there wont be anymore char1's to increate the difference.
                        # we break instead of trying to store the difference somewhere because
                        # with the use of permutations, we compare the difference on 'a', 'b', and 'b', 'a',
                        # so each character has an opportunity to be char 1 and char 2
                        break
                    
                    if not char2_count:
                        # we finish our iteration of the string here and try to get the best result
                        # there is no need to continue looping over the string, because we ran out of
                        # the char2's that we will see. because of this, we use the remaining char1's
                        # that are yet to be seen to increase the difference. its a case like
                        # bbbxyza, where a is char 1 and b is char 2. when we get to x, char 2 count is 0
                        # but char 1 count is still 1, so we forget iterating over xyz and just add char 1
                        # count to the difference. we wont see any more b's in the search for a's when we reach x.
                        result = max(result, difference + char1_count)
                        break
                    
                    difference = 0
                    # we are still in the if statement, which is true when there is a negative difference.
                    # which only happens when char2 is greater than char1. because we iterate over every
                    # permutation, we want to calculate the difference between char1 and char2, where char1 is
                    # ideally largest and char2 is the smallest. we dont need to worry about vice-versa because
                    # with permutations, char1 and char2's values will eventually be switched and compared
                    # with our logic.
                    # at this point, there is still char1 and char2's to be seen, so we just reset, and hope to
                    # get a larger value. this resetting logic has been seen before in "Maximum Subarray"
                    seen_char1 = False
                    seen_char2 = False
                
                # the below calculates the difference, where the difference is positive if there is more
                # char1 than char2
                if current == char1:
                    difference += 1
                    char1_count -= 1
                    seen_char1 = True

                if current == char2:
                    difference -= 1
                    char2_count -= 1
                    seen_char2 = True

                # we need the boolean check here because in the case of
                # "axyzb", if we are comparing a and b, without the if statement
                # the logic would assign 1 to "result" after seeing the first "a"
                # and having not yet seen the "b". we only care to keep track of the
                # difference between 2 characters after they have both been seen.
                # the difference betweeen a and b in "aaabbb" is 0, but without the
                # if statement we would mistakenly assign 3 to result.
                if seen_char1 and seen_char2:
                    result = max(result, difference)
        
        return result

2088