1
/*
2
    Time: O(26*26*n)
3
    Space: O(1)
4
    Tag: Kadane's Algorithm
5
    Difficulty: H (Logic) | E(Implementation)
6
*/
7

8
class Solution {
9
 public:
10
  int largestVariance(string s) {
11
    int res = 0;
12
    for (int i = 0; i < 26; i++) {
13
      for (int j = 0; j < 26; j++) {
14
        if (i == j) continue;
15
        int highFreq = 0;
16
        int lowFreq = 0;
17
        bool prevHadLowFreqChar = false;
18
        for (char ch : s) {
19
          if (ch - 'a' == i)
20
            highFreq++;
21
          else if (ch - 'a' == j)
22
            lowFreq++;
23
          if (lowFreq > 0)
24
            res = max(res, highFreq - lowFreq);
25
          else if (prevHadLowFreqChar)
26
            res = max(res, highFreq - 1);
27
          if (highFreq - lowFreq < 0) {
28
            highFreq = 0;
29
            lowFreq = 0;
30
            prevHadLowFreqChar = true;
31
          }
32
        }
33
      }
34
    }
35
    return res;
36
  }
37
};