LeetCode 2272. Substring With Largest Variance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
int largestVariance(string s) {
int ans = 0;
unordered_set<char> unique(s.begin(), s.end());
// go through each possibilities to find the ans.
for (char a : unique)
for (char b : unique) {
if (a == b) continue;
int var = 0, has_b = 0, first_b = 0;
for (auto ch : s) {
// var is used to track the occurrences diff between "a" and "b".
if (ch == a) ++var;
else if (ch == b) {
has_b = true;
// we are having a leading "b" and now one more "b" with cnt(a) >= cnt(b),
// so we can cut the leading "b" for a better ans.
if (first_b && var >= 0) first_b = false;
// "--var < 0" indicates that we are having too many "b(s)" here,
// so we take this "b" as a fresh start.
else if (--var < 0) first_b = true, var = -1;
}
// update the ans if and only if "b" is within the substr.
ans = max(ans, has_b ? var : 0);
}
}
return ans;
}
};

Reference: Weird Kadane - LeetCode Discuss.