# Substring With Largest Variance
**Difficulty:** HARD
[External](https://leetcode.com/problems/substring-with-largest-variance)
Canonical: https://scaleengineer.com/dsa/problems/substring-with-largest-variance
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
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.

**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.

**Constraints:**

* `1 <= s.length <= 104`
* `s` consists of lowercase English letters.

# Approaches
## Brute Force
The most straightforward approach is to check every single possibility. We can generate all substrings of the input string `s`. For each of these substrings, we then calculate its variance. To calculate the variance of a substring, we find the frequency of all characters within it and then compute the difference in counts for every possible pair of characters, keeping track of the maximum difference found.
**Time:** O(N³), where N is the length of the string. There are O(N²) substrings. For each substring of length L, it takes O(L) to build the frequency map. Since L can be up to N, this results in an O(N³) complexity. The final loops over character pairs are constant time (26*26). · **Space:** O(1), as the frequency map has a constant size of 26.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient and will time out for the given constraints.
### Explanation
This method involves three nested loops. The outer two loops define the start and end points of a substring. The third, inner loop (or equivalent operation) iterates through the substring to build a frequency count of its characters. After counting, two more loops iterate through all 26*26 pairs of characters to find the maximum difference in frequencies.

```java
class Solution {
    public int largestVariance(String s) {
        int maxVariance = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = s.substring(i, j + 1);
                int[] freq = new int[26];
                for (char c : sub.toCharArray()) {
                    freq[c - 'a']++;
                }

                for (int c1 = 0; c1 < 26; c1++) {
                    for (int c2 = 0; c2 < 26; c2++) {
                        if (freq[c1] > 0 && freq[c2] > 0) {
                           maxVariance = Math.max(maxVariance, freq[c1] - freq[c2]);
                        }
                    }
                }
            }
        }
        return maxVariance;
    }
}
```
Note: The condition `freq[c1] > 0 && freq[c2] > 0` ensures both characters are present in the substring. If the problem allows for a character not present (count 0), this check can be simplified.
### Algorithm
1. Generate all possible substrings of the input string `s`.
2. For each substring:
   a. Create a frequency map (e.g., an array of size 26) to count the occurrences of each character in the substring.
   b. Iterate through all possible pairs of characters (`char1`, `char2`).
   c. Calculate the variance for the pair: `frequency[char1] - frequency[char2]`.
   d. Keep track of the maximum variance found across all substrings and all character pairs.
3. Return the overall maximum variance.

## Improved Brute Force
We can optimize the brute-force approach by improving how we calculate character frequencies. Instead of recounting characters for every substring, we can iterate through all possible start points. For each start point, we extend the substring one character at a time, updating the frequency map incrementally. This avoids the redundant counting of the previous approach.
**Time:** O(N²). The two nested loops for `i` and `j` give O(N²). The inner operations (updating frequency and checking all 26*26 pairs) take constant time. · **Space:** O(1), for the frequency map.
**Pros:** More efficient than the naive brute-force approach.
**Cons:** Still too slow for the given constraints, likely to result in a Time Limit Exceeded error.
### Explanation
This approach reduces the complexity of calculating frequencies. For a fixed starting point `i`, as we extend the end point `j`, we only need to account for the new character `s.charAt(j)`. This brings the complexity of handling all substrings starting at `i` down to O(N). Since we do this for all N possible start points, the total complexity is improved.

```java
class Solution {
    public int largestVariance(String s) {
        int maxVariance = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - 'a']++;
                // Now freq is for substring s[i..j]
                for (int c1 = 0; c1 < 26; c1++) {
                    for (int c2 = 0; c2 < 26; c2++) {
                        if (freq[c1] > 0 && freq[c2] > 0) {
                            maxVariance = Math.max(maxVariance, freq[c1] - freq[c2]);
                        }
                    }
                }
            }
        }
        return maxVariance;
    }
}
```
### Algorithm
1. Iterate through all possible starting positions `i` of a substring.
2. For each `i`, start a second loop for the ending position `j` from `i` to the end of the string.
3. Maintain a frequency map for the current substring `s.substring(i, j+1)`. Instead of rebuilding it for each substring, initialize it at the start of the outer loop and update it by one character as `j` increments.
4. For each substring defined by `(i, j)`, iterate through all character pairs to find the maximum frequency difference and update the global maximum variance.
5. Return the global maximum variance.

## Kadane's Algorithm for Each Character Pair
A much more efficient approach is to change the perspective. Instead of iterating through substrings, we iterate through all possible pairs of characters (`c1`, `c2`) that could produce the variance. For each fixed pair, we aim to find a substring that maximizes `count(c1) - count(c2)`. This subproblem can be solved in linear time using a modified version of Kadane's algorithm.
**Time:** O(N). The main loop iterates through all 26*26 pairs of characters, which is a constant factor (C = 26*26). For each pair, we perform a linear scan (O(N)) of the string twice. Thus, the total time complexity is O(C * N), which simplifies to O(N). · **Space:** O(N) if we consider the space for the reversed string. If the string is reversed in-place or iterated backwards with an index, space complexity can be O(1).
**Pros:** Highly efficient and passes within the time limits.; Reduces the problem to a known pattern (Kadane's algorithm).
**Cons:** The logic for the modified Kadane's algorithm is complex and non-trivial to derive correctly.
### Explanation
For a fixed pair of characters, say `major = 'a'` and `minor = 'b'`, we want to find a substring with the maximum value of `count('a') - count('b')`. We can iterate through the string, maintaining a running count for `major` and `minor`. Let these be `majorCount` and `minorCount`.

The variance is updated whenever we have seen at least one of each character (`majorCount > 0` and `minorCount > 0`). A key part of this modified Kadane's algorithm is the reset condition. If `majorCount < minorCount`, it's often better to start a new substring, so we reset both counts to zero. However, this greedy reset can fail if the optimal substring has a prefix that meets this condition. For example, in `s = "ababbb"` and pair `('b', 'a')`, the optimal substring is `"babbb"` (variance 2), but the algorithm might incorrectly reset after processing the prefix `"aba"`.

To solve this, the entire procedure is run twice for each pair: once on the string from left-to-right, and once from right-to-left (by reversing the string). This ensures that no matter how the optimal substring is structured, one of the two passes will find it correctly.

```java
class Solution {
    public int largestVariance(String s) {
        int maxVariance = 0;
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        for (char c1 = 'a'; c1 <= 'z'; c1++) {
            for (char c2 = 'a'; c2 <= 'z'; c2++) {
                if (c1 == c2 || freq[c1 - 'a'] == 0 || freq[c2 - 'a'] == 0) {
                    continue;
                }
                // Run modified Kadane's for this pair
                maxVariance = Math.max(maxVariance, calculateVarianceForPair(s, c1, c2));
            }
        }
        return maxVariance;
    }

    private int calculateVarianceForPair(String s, char c1, char c2) {
        int maxVariance = 0;
        int count1 = 0, count2 = 0;
        // Run twice, once forward, once backward (by reversing the string)
        for (int run = 0; run < 2; run++) {
            count1 = 0;
            count2 = 0;
            for (char ch : s.toCharArray()) {
                if (ch == c1) {
                    count1++;
                } else if (ch == c2) {
                    count2++;
                }

                if (count1 > 0 && count2 > 0) {
                    maxVariance = Math.max(maxVariance, count1 - count2);
                }

                if (count1 < count2) {
                    count1 = 0;
                    count2 = 0;
                }
            }
            // Reverse the string for the second run
            s = new StringBuilder(s).reverse().toString();
        }
        return maxVariance;
    }
}
```
### Algorithm
1. The core idea is to fix the two characters (`c1` and `c2`) for which we want to maximize the count difference (`count(c1) - count(c2)`).
2. Iterate through all 26 * 25 possible pairs of distinct characters (`c1` as the character with higher frequency, `c2` with lower).
3. For each pair, iterate through the string `s` to find the maximum variance for just these two characters. This subproblem is equivalent to finding the maximum subarray sum, a problem that can be solved with Kadane's algorithm.
4. We treat `c1` as `+1` and `c2` as `-1`. The challenge is that the substring must contain at least one of each character.
5. A modified Kadane's algorithm is used. We maintain counts for `c1` and `c2`. If `count2` becomes greater than `count1`, it's detrimental to extend the current substring, so we reset the counts, effectively starting a new substring.
6. An issue with this reset is that an optimal substring might have a prefix where `count2 > count1`. To handle this, the process is run twice for each pair: once on the original string and once on its reverse. This ensures we capture all cases.
7. The overall maximum variance is the maximum found across all character pairs and both passes (forward and backward).

# Solutions
### Java

```java
class Solution {
public
  int largestVariance(String s) {
    int n = s.length();
    int ans = 0;
    for (char a = 'a'; a <= 'z'; ++a) {
      for (char b = 'a'; b <= 'z'; ++b) {
        if (a == b) {
          continue;
        }
        int[] f = new int[]{0, -n};
        for (int i = 0; i < n; ++i) {
          if (s.charAt(i) == a) {
            f[0]++;
            f[1]++;
          } else if (s.charAt(i) == b) {
            f[1] = Math.max(f[0] - 1, f[1] - 1);
            f[0] = 0;
          }
          ans = Math.max(ans, f[1]);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: int largestVariance ( string s ) { int n = s . size (); int ans = 0 ; for ( char a = 'a' ; a <= 'z' ; ++ a ) { for ( char b = 'a' ; b <= 'z' ; ++ b ) { if ( a == b ) continue ; int f [ 2 ] = { 0 , - n }; for ( char c : s ) { if ( c == a ) { f [ 0 ] ++ ; f [ 1 ] ++ ; } else if ( c == b ) { f [ 1 ] = max ( f [ 1 ] - 1 , f [ 0 ] - 1 ); f [ 0 ] = 0 ; } ans = max ( ans , f [ 1 ]); } } } return ans ; } };
```

### Python

```python
class Solution : def largestVariance ( self , s : str ) -> int : ans = 0 for a , b in permutations ( ascii_lowercase , 2 ): if a == b : continue f = [ 0 , - inf ] for c in s : if c == a : f [ 0 ], f [ 1 ] = f [ 0 ] + 1 , f [ 1 ] + 1 elif c == b : f [ 1 ] = max ( f [ 1 ] - 1 , f [ 0 ] - 1 ) f [ 0 ] = 0 if ans < f [ 1 ]: ans = f [ 1 ] return ans
```