<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:
    # # approach 1: Kadane's Algo (DP) - O(26^2 * N), O(N)
    # def largestVariance(self, s: str) -> int:
    #     n = len(s)
    #     res = 0
        
    #     for a, b in itertools.permutations(Counter(s), 2): # pick a pair
    #         # -1 represents a, the more frequent character
    #         # 1 represents b, the less frequent character
    #         # use dp vars instead of tables to save space
    #         dp0 = 0 # greatest variance for substring ending at i without -1 
    #         dp1 = -10**4 # greatest variance for substring ending at i with -1
    #         # for i in range(n): # TLE
    #         for char in s: # no TLE
    #             if char != a and char != b:
    #                 continue
    #             if char == a:
    #                 dp0 += 1
    #                 dp1 += 1
    #             elif char == b:
    #                 # assignment order matters here!
    #                 dp1 = max(dp1 - 1, dp0 - 1)
    #                 dp0 = 0 # all chars in substring are 1, invalid
    #             res = max(res, dp1)
    #     return res
    
    # approach 2: Kadane's Algo - O(), O()
    def largestVariance(self, s: str) -> int:
        counts = collections.Counter(s)

        def kadane(major, minor):
            res = 0
            diff = 0 # variance between major and minor occurrences
            minor_seen = 0 # # of minor seen so far
            minor_remain = counts[minor] # # of minor remaining

            # -1 contribution to variance made by minor
            # +1 contribution to variance made by major
            for c in s:
                if c == minor:
                    diff -= 1
                    minor_seen += 1
                    minor_remain -= 1
                if c == major:
                    diff += 1
                # reset counting
                if diff < 0 and minor_remain:
                    # minor more than major and minor remaining, reset countin
                    diff = 0
                    minor_seen = 0
                # ensure solution's substring has minor char
                if minor_seen:
                    res = max(res, diff)
            
            return res
        
        res = 0
        for c0, c1 in itertools.permutations(counts, 2):
            if c0 != c1:
                res = max(res, kadane(c0, c1))
        return res
4506