Substring With Largest Variance — Problem & Solution
Substring With Largest Variance solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Substring With Largest Variance is a hard coding problem on arrays and dynamic programming, asked in Amazon and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The variance of a string is the largest difference between the number of occurrences of any two characters present in it (the two characters may be the same, giving 0).
Given a string s of lowercase English letters, return the largest variance over all of its substrings. A substring is a contiguous, non-empty run of characters.
Example 1
Input: s = "aababbb"
Output: 3
Explanation: In "babbb", 'b' appears 4 times and 'a' once: variance 3.
Example 2
Input: s = "abcde"
Output: 0
Explanation: Every letter appears at most once in any substring.
Example 3
Input: s = "aaaa"
Output: 0
Explanation: With a single distinct letter, the only difference is 0.
Constraints
1 <= s.length <= 10^4s consists of lowercase English letters
Hints for Substring With Largest Variance
Hint 1
The answer is achieved by some pair of letters:
athe most frequent andbthe least frequent in the best substring. There are only26 * 25ordered pairs.Hint 2
For a fixed pair, map
ato+1,bto-1and every other letter to0. The variance of a substring is its sum — but only if the substring contains at least oneb.Hint 3
Run Kadane's maximum-subarray scan for each pair, tracking whether the current window holds a
b. Reset the window when the count ofbexceedsaonly if anotherbis still ahead in the string.
How to solve Substring With Largest Variance
Fix which letter should be most frequent (a) and which least frequent (b). The substring's score is count(a) - count(b) with at least one b present — a maximum-subarray problem with an extra condition, solved by a modified Kadane scan for each of the 650 pairs.
Approach
- For every ordered pair
(a, b)of distinct letters that both occur ins: - Scan
skeepingcaandcb(counts in the current window) andrestB(occurrences ofbnot yet scanned). - On
a,ca++; onb,cb++andrestB--. Whenevercb > 0, update the answer withca - cb. - If
ca < cbandrestB > 0, reset both counts to 0 — a window starting later can do better and will still find ab. - Return the best value seen.
Why it works
For the optimal substring, its most and least frequent present letters form one of the pairs, and its variance equals that pair's +1/-1 sum, so maximising every pair's constrained sum covers the optimum (and never overshoots, since each pair's sum is at most the true variance of that substring). The reset is Kadane's rule — a negative prefix never helps — except that dropping the window's only b would lose the condition, which is why a reset waits until another b remains.
Complexity
- Time —
O(26 * 26 * n) - Space —
O(1)
Pitfalls
- A window with no
bdoes not count: "aaaa" scores 0, not 4. - Resetting whenever
ca < cbloses windows like "baaa": keep thebwhen it is the last one available. - Skip pairs whose letters do not both occur — otherwise the 26×26 loop dominates on short strings.
Reference solution
Python
def largestVariance(s: str) -> int:
present = sorted(set(s))
best = 0
for a in present:
for b in present:
if a == b:
continue
rest_b = s.count(b)
ca = cb = 0
for ch in s:
if ch == a:
ca += 1
elif ch == b:
cb += 1
rest_b -= 1
else:
continue
if cb > 0 and ca - cb > best:
best = ca - cb
if ca < cb and rest_b > 0:
ca = cb = 0
return bestJava
public static int largestVariance(String s) {
int n = s.length(), best = 0;
int[] total = new int[26];
for (int i = 0; i < n; i++) total[s.charAt(i) - 'a']++;
for (int a = 0; a < 26; a++) {
if (total[a] == 0) continue;
for (int b = 0; b < 26; b++) {
if (a == b || total[b] == 0) continue;
int ca = 0, cb = 0, restB = total[b];
for (int i = 0; i < n; i++) {
int c = s.charAt(i) - 'a';
if (c == a) ca++;
else if (c == b) { cb++; restB--; }
else continue;
if (cb > 0) best = Math.max(best, ca - cb);
if (ca < cb && restB > 0) { ca = 0; cb = 0; }
}
}
}
return best;
}C++
int largestVariance(string s) {
int n = s.size(), best = 0;
int total[26] = {0};
for (char ch : s) total[ch - 'a']++;
for (int a = 0; a < 26; a++) {
if (!total[a]) continue;
for (int b = 0; b < 26; b++) {
if (a == b || !total[b]) continue;
int ca = 0, cb = 0, restB = total[b];
for (int i = 0; i < n; i++) {
int c = s[i] - 'a';
if (c == a) ca++;
else if (c == b) { cb++; restB--; }
else continue;
if (cb > 0) best = max(best, ca - cb);
if (ca < cb && restB > 0) { ca = 0; cb = 0; }
}
}
}
return best;
}JavaScript
var largestVariance = function(s) {
var total = new Array(26).fill(0), n = s.length, best = 0;
var codes = new Array(n);
for (var i = 0; i < n; i++) { codes[i] = s.charCodeAt(i) - 97; total[codes[i]]++; }
for (var a = 0; a < 26; a++) {
if (!total[a]) continue;
for (var b = 0; b < 26; b++) {
if (a === b || !total[b]) continue;
var ca = 0, cb = 0, restB = total[b];
for (var i = 0; i < n; i++) {
var c = codes[i];
if (c === a) ca++;
else if (c === b) { cb++; restB--; }
else continue;
if (cb > 0 && ca - cb > best) best = ca - cb;
if (ca < cb && restB > 0) { ca = 0; cb = 0; }
}
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming