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

Given a string s consisting of lowercase English letters only, return the largest variance possible among all substrings of s.

A substring is a contiguous sequence of characters within a string.

&nbsp;
Example 1:

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


Example 2:

Input: s = "abcde"
Output: 0
Explanation:
No letter occurs more than once in s, so the variance of every substring is 0.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 104
	s consists of lowercase English letters.


class Solution:
    class Solution:
    def largestVariance(self, s: str) -> int:
        
        def maxSubArray(nums: List[int]):
            ans=-float('inf')
            runningSum=0
            seen=False
            for x in (nums):
                if x<0:
                    seen=True
                runningSum+=x
                if seen:
                    ans=max(ans,runningSum)
                else:
                    ans=max(ans,runningSum-1)
                if runningSum<0:
                    runningSum=0
                    seen=False
            return ans
        
        f=set()
        a=''
        for x in s:
            if x not in f:
                a+=x
                f.add(x)
       
        n=len(s)
        res=0
        for j in range(len(a)-1):
            for k in range(j+1,len(a)):
                x=a[j]
                y=a[k]
                arr=[]
                for i in range(n):
                    if s[i]!=x and s[i]!=y:
                        continue
                    elif s[i]==x:
                        arr.append(1)
                    else:
                        arr.append(-1)
                
                res=max(res,maxSubArray(arr),maxSubArray([-x for x in arr]))
                
        return res
                
                
                
                
class Solution {
    public int largestVariance(String s) {
        
        int [] freq = new int[26];
        for(int i = 0 ; i < s.length() ; i++)
            freq[(int)(s.charAt(i) - 'a')]++;
        
        int maxVariance = 0;
        for(int a = 0 ; a < 26 ; a++){
            for(int b = 0 ; b < 26 ; b++){
                int remainingA = freq[a];
                int remainingB = freq[b];
                if(a == b || remainingA == 0 || remainingB == 0) continue;
                
				// run kadanes on each possible character pairs (A & B)
                int currBFreq = 0, currAFreq = 0;
                for(int i = 0 ; i < s.length() ; i++){
                    int c =  (int)(s.charAt(i) - 'a');
                    
                    if(c == b) currBFreq++;
                    if(c == a) {
                        currAFreq++;
                        remainingA--;
                    }
                    
                    if(currAFreq > 0)
                        maxVariance = Math.max(maxVariance, currBFreq - currAFreq);
                    
                    if(currBFreq < currAFreq &&  remainingA >= 1){
                        currBFreq = 0;
                        currAFreq = 0;
                    }
                }
            }
        }
        
        return maxVariance;
    }
}
/*
    Time: O(26*26*n)
    Space: O(1)
    Tag: Kadane's Algorithm
    Difficulty: H (Logic) | E(Implementation)
*/

class Solution {
public:
    int largestVariance(string s) {
        int res = 0;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                if (i == j) continue;
                int highFreq = 0;
                int lowFreq = 0;
                bool prevHadLowFreqChar = false;
                for (char ch : s) {
                    if (ch - 'a' == i)
                        highFreq++;
                    else if (ch - 'a' == j)
                        lowFreq++;
                    if (lowFreq > 0)
                        res = max(res, highFreq - lowFreq);
                    else if (prevHadLowFreqChar)
                        res = max(res, highFreq - 1);
                    if (highFreq - lowFreq < 0) {
                        highFreq = 0;
                        lowFreq = 0;
                        prevHadLowFreqChar = true;
                    }
                }
            }
        }
        return res;
    }
};
var largestVariance = function(s) {
  let chars = new Set(s.split("")), maxDiff = 0;
  for (let l of chars) {
    for (let r of chars) {
      if (l === r) continue;
      let lCount = 0, rCount = 0, hasRight = false;
      for (let char of s) {
        lCount += char === l ? 1 : 0;
        rCount += char === r ? 1 : 0;
        if (rCount > 0 && lCount > rCount) { // has both characters and positive difference
          maxDiff = Math.max(maxDiff, lCount - rCount);
        }
        if (lCount > rCount && hasRight) { // has positive difference and a previous "right" character we can add to the start
          maxDiff = Math.max(maxDiff, lCount - rCount - 1);
        }
        if (lCount < rCount) {
          lCount = 0, rCount = 0;
          hasRight = true;
        }
      }
    }
  }
  return maxDiff;
};
Substring With Largest Variance