1
class Solution {
2
  public int largestVariance(String s) {
3

4
    int[] freq = new int[26];
5
    for (int i = 0; i < s.length(); i++) freq[(int) (s.charAt(i) - 'a')]++;
6

7
    int maxVariance = 0;
8
    for (int a = 0; a < 26; a++) {
9
      for (int b = 0; b < 26; b++) {
10
        int remainingA = freq[a];
11
        int remainingB = freq[b];
12
        if (a == b || remainingA == 0 || remainingB == 0) continue;
13

14
        // run kadanes on each possible character pairs (A & B)
15
        int currBFreq = 0, currAFreq = 0;
16
        for (int i = 0; i < s.length(); i++) {
17
          int c = (int) (s.charAt(i) - 'a');
18

19
          if (c == b) currBFreq++;
20
          if (c == a) {
21
            currAFreq++;
22
            remainingA--;
23
          }
24

25
          if (currAFreq > 0) maxVariance = Math.max(maxVariance, currBFreq - currAFreq);
26

27
          if (currBFreq < currAFreq && remainingA >= 1) {
28
            currBFreq = 0;
29
            currAFreq = 0;
30
          }
31
        }
32
      }
33
    }
34

35
    return maxVariance;
36
  }
37
}