Maximize the Difference between Two Present Letter Counts
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
For a nonempty contiguous substring of lowercase string `s`, choose two letters present in that substring and subtract the smaller occurrence count from the larger. You may choose the same letter twice, giving a difference of zero. Return the greatest difference obtainable over all substrings.
```cpp
class Solution {
public:
int largestVariance(string s);
};
```
### Examples
**Example 1:**
```text
Input: s = "caaac"
Output: 2
Explanation: The substring "caaa" contains three a letters and one c, for variance 2. No substring has more than three a letters.
```
**Example 2:**
```text
Input: s = "zzzz"
Output: 0
Explanation: Only one letter is present in every substring. Comparing its count with itself gives zero.
```
### Constraints
- `1 <= s.length <= 10000`.
- s contains lowercase English letters.
### Clarifying Questions
- Can an absent letter supply a count of zero? No; both selected letters must be present.
- Are single-letter substrings allowed? Yes; their variance is zero.
- Must a substring or pair of letters be returned? No, return only the greatest difference.
```hint Check the boundary
Distinguish a count of zero for an absent letter from choosing the same present letter twice.
```
Overview: Find the largest difference between counts of two present letters over all contiguous substrings of a lowercase string.
