Substring With Largest Variance solution and explanation
9 more videos on this problem
Substring With Largest Variance | 2272 LeetCode | Maths | Leetcode Biweekly Contest 78CodeWithSunny · 18:36 · 12K views
Substring With Largest Variance | Full Dry Run | Leetcode-2272 | AMAZON | GOOGLE | ExplanationcodestorywithMIK · 40:29 · 11K views
Substring With Largest Variance II Modified Kadanes Algorithm II Leetcode 2272Aryan Mittal · 33:13 · 6K views
2272. Substring With Largest Variance (Leetcode Hard)Programming Live with Larry · 1:44:54 · 4K views
SUBSTRING WITH LARGEST VARIANCE | LEETCODE 2272 | PYTHON | AMAZON'S TOP INTERVIEW QUESTIONCracking FAANG · 16:38 · 4K views
Substring With Largest Variance - Leetcode 2272 - PythonTechError · 9:52 · 3K views
Leetcode Biweekly contest 78 Hard - Substring With Largest VariancePrakhar Agrawal · 17:16 · 2K views
Leetcode 2272. Substring With Largest Variance - Kadane's algorithmCode-Yao · 21:41 · 2K views
Substring With Largest Variance | Google |Daily Leetcode Challenge | Leetcode 2272| HardLet's Code Together · 11:32 · 1K views
Substring With Largest Variance - LeetCode 2272 - PythonAlpha-Code · 20:33 · 531 views
The 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 <= 104sconsists of lowercase English letters.
Approach overview
Problem Overview: Given a string s, find a substring where the difference between the frequency of two characters is maximized. The variance of a substring is defined as count(a) - count(b) for two characters that both appear in the substring.
Approach 1: Kadane's Algorithm for Character Pair (O(26² · n) time, O(1) space)
The key observation: variance only depends on two characters at a time. Iterate over every ordered pair of characters (a, b). Treat occurrences of a as +1 and b as -1, ignoring other characters. Now the problem becomes a modified maximum subarray problem, which can be solved using Kadane’s algorithm. While scanning the string, track the running sum and ensure the substring includes at least one b. If the running score becomes negative and more b characters remain ahead, reset the window. This ensures we only keep promising candidates while respecting the requirement that both characters appear.
This approach effectively runs Kadane’s algorithm for all 26 × 26 ordered character pairs. Since each pass scans the string once, the total time complexity is O(26² · n), which is effectively linear for lowercase strings. The algorithm uses constant extra memory because only counters and running sums are stored. This technique combines ideas from Array traversal and dynamic score tracking similar to Dynamic Programming.
Approach 2: Sliding Window Technique (O(26² · n) time, O(1) space)
Another way to think about the problem is maintaining a window that contains two characters while maximizing their count difference. For every character pair (a, b), expand a window across the string and maintain counts of both characters. When the count of b dominates too heavily, shrink or reset the window since the variance would become negative and unlikely to produce a better answer. This behaves similarly to Kadane’s reset rule but is implemented with explicit window boundaries and counters.
The sliding window perspective is useful if you prefer thinking in terms of substring ranges rather than cumulative scores. Each iteration updates counts and computes count(a) - count(b) while ensuring both characters appear at least once. Although implemented differently, the time complexity remains O(26² · n) because the algorithm still evaluates every character pair and scans the string once per pair. Space usage remains O(1).
Recommended for interviews: The Kadane-based solution is what most interviewers expect. It demonstrates the ability to reduce a substring optimization problem into a maximum subarray variant and shows strong understanding of state resets and pairwise enumeration. Explaining the brute intuition (checking character pairs) first, then deriving the Kadane transformation, clearly signals strong problem-solving skills.
Approach 1: Kadane's Algorithm for Character Pair
This approach leverages a modified version of Kadane's algorithm to find the largest variance by calculating frequency differences for each character pair combination. We'll use a variation of Kadane's approach to track the balance difference in frequencies between two characters across the string.
def largestVariance(s: str) -> int:
maxVariance = 0
for a in set(s):
for b in set(s):
if a == b:
continue
countA = countB = 0
for char in s:
if char == a:
countA += 1
if char == b:
countB += 1
if countB > 0:
maxVariance = max(maxVariance, countA - countB)
else:
maxVariance = max(maxVariance, countA)
if countA < countB:
countA = countB = 0
return maxVariance
print(largestVariance("aababbb")) # Output: 3public class LargestVariance {
public static int largestVariance(String s) {
int maxVariance = 0;
int n = s.length();
for (char a = 'a'; a <= 'z'; a++) {
for (char b = 'a'; b <= 'z'; b++) {
if (a == b) continue;
int countA = 0, countB = 0;
int maxBal = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == a) countA++;
if (s.charAt(i) == b) countB++;
if (countB > 0) {
maxVariance = Math.max(maxVariance, countA - countB);
} else {
maxVariance = Math.max(maxVariance, countA);
}
if (countA < countB) {
countA = 0; countB = 0;
}
}
}
}
return maxVariance;
}
public static void main(String[] args) {
System.out.println(largestVariance("aababbb")); // Output: 3
}
}#include <iostream>
#include <string>
#include <climits>
using namespace std;
int largestVariance(string s) {
int maxVariance = 0;
int n = s.length();
for (char a = 'a'; a <= 'z'; a++) {
for (char b = 'a'; b <= 'z'; b++) {
if (a == b) continue;
int countA = 0, countB = 0;
int maxBal = INT_MIN;
for (int i = 0; i < n; i++) {
if (s[i] == a) countA++;
if (s[i] == b) countB++;
if (countB > 0) {
maxVariance = max(maxVariance, countA - countB);
} else {
maxVariance = max(maxVariance, countA);
}
if (countA < countB) {
countA = 0; countB = 0;
}
}
}
}
return maxVariance;
}
int main() {
cout << largestVariance("aababbb") << endl; // Output: 3
return 0;
}function largestVariance(s) {
let maxVariance = 0;
const n = s.length;
for (let a = 'a'.charCodeAt(0); a <= 'z'.charCodeAt(0); a++) {
for (let b = 'a'.charCodeAt(0); b <= 'z'.charCodeAt(0); b++) {
if (a === b) continue;
let [countA, countB] = [0, 0];
for (let i = 0; i < n; i++) {
if (s.charCodeAt(i) === a) countA++;
if (s.charCodeAt(i) === b) countB++;
if (countB > 0) {
maxVariance = Math.max(maxVariance, countA - countB);
} else {
maxVariance = Math.max(maxVariance, countA);
}
if (countA < countB) {
countA = countB = 0;
}
}
}
}
return maxVariance;
}
console.log(largestVariance("aababbb")); // Output: 3#include <stdio.h>
#include <string.h>
#include <limits.h>
int largestVariance(char *s) {
int maxVariance = 0;
int n = strlen(s);
for (char a = 'a'; a <= 'z'; a++) {
for (char b = 'a'; b <= 'z'; b++) {
if (a == b) continue;
int countA = 0, countB = 0;
int maxBal = INT_MIN;
for (int i = 0; i < n; i++) {
if (s[i] == a) countA++;
if (s[i] == b) countB++;
if (countB > 0) {
maxVariance = maxVariance > (countA - countB) ?
maxVariance : (countA - countB);
} else {
/* Reset when negative or zero to avoid excessive penalizing */
maxVariance = maxVariance > countA ? maxVariance : countA;
}
if (countA < countB) {
countA = 0; countB = 0;
}
}
}
}
return maxVariance;
}
int main() {
char s[] = "aababbb";
printf("%d\n", largestVariance(s)); // Output: 3
return 0;
}using System;
public class Program
{
public static int LargestVariance(string s)
{
int maxVariance = 0;
int n = s.Length;
for (char a = 'a'; a <= 'z'; a++)
{
for (char b = 'a'; b <= 'z'; b++)
{
if (a == b) continue;
int countA = 0, countB = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == a) countA++;
if (s[i] == b) countB++;
if (countB > 0)
{
maxVariance = Math.Max(maxVariance, countA - countB);
}
else
{
maxVariance = Math.Max(maxVariance, countA);
}
if (countA < countB)
{
countA = 0; countB = 0;
}
}
}
}
return maxVariance;
}
public static void Main()
{
Console.WriteLine(LargestVariance("aababbb")); // Output: 3
}
}This Python solution iterates over each distinct character combination found in the string. The implementation assesses current balance using a frequency count strategy, regulating resets for most effective results.
The time complexity is O(n), driven by pairwise evaluations while efficiently iterating through characters. The space complexity is O(1) for constant space usage.
Approach 2: Sliding Window Technique
The second approach is using the sliding window technique, which dynamically adjusts the window as we scan through the string. This helps to efficiently find all possible maximum variances for character combinations by maintaining two counters and extending or shrinking the window as needed.
def largestVarianceSlidingWindow(s: str) -> int:
maxVariance = 0
n = len(s)
for a in set(s):
for b in set(s):
if a == b:
continue
countA = countB = 0
start = 0
for end in range(n):
if s[end] == a:
countA += 1
if s[end] == b:
countB += 1
if countB > 0:
maxVariance = max(maxVariance, countA - countB)
if countA < countB:
while start <= end:
if s[start] == a:
countA -= 1
if s[start] == b:
countB -= 1
start += 1
return maxVariance
print(largestVarianceSlidingWindow("aababbb")) # Output: 3public class LargestVarianceSlidingWindow {
public static int largestVarianceSlidingWindow(String s) {
int maxVariance = 0;
int n = s.length();
for (char a = 'a'; a <= 'z'; a++) {
for (char b = 'a'; b <= 'z'; b++) {
if (a == b) continue;
int windowA = 0, windowB = 0, start = 0;
for (int end = 0; end < n; end++) {
if (s.charAt(end) == a) windowA++;
if (s.charAt(end) == b) windowB++;
if (windowB > 0) {
maxVariance = Math.max(maxVariance, windowA - windowB);
}
if (windowA < windowB) {
while (start <= end) {
if (s.charAt(start) == a) windowA--;
if (s.charAt(start) == b) windowB--;
start++;
}
}
}
}
}
return maxVariance;
}
public static void main(String[] args) {
System.out.println(largestVarianceSlidingWindow("aababbb")); // Output: 3
}
}#include <iostream>
#include <string>
using namespace std;
int largestVarianceSlidingWindow(string s) {
int maxVariance = 0;
int n = s.length();
for (char a = 'a'; a <= 'z'; a++) {
for (char b = 'a'; b <= 'z'; b++) {
if (a == b) continue;
int windowA = 0, windowB = 0, start = 0;
for (int end = 0; end < n; end++) {
if (s[end] == a) windowA++;
if (s[end] == b) windowB++;
if (windowB > 0) {
maxVariance = max(maxVariance, windowA - windowB);
}
if (windowA < windowB) {
while (start <= end) {
if (s[start] == a) windowA--;
if (s[start] == b) windowB--;
start++;
}
}
}
}
}
return maxVariance;
}
int main() {
cout << largestVarianceSlidingWindow("aababbb") << endl; // Output: 3
return 0;
}function largestVarianceSlidingWindow(s) {
let maxVariance = 0;
const n = s.length;
for (let a = 'a'.charCodeAt(0); a <= 'z'.charCodeAt(0); a++) {
for (let b = 'a'.charCodeAt(0); b <= 'z'.charCodeAt(0); b++) {
if (a === b) continue;
let [windowA, windowB, start] = [0, 0, 0];
for (let end = 0; end < n; end++) {
if (s.charCodeAt(end) === a) windowA++;
if (s.charCodeAt(end) === b) windowB++;
if (windowB > 0) {
maxVariance = Math.max(maxVariance, windowA - windowB);
}
if (windowA < windowB) {
while (start <= end) {
if (s.charCodeAt(start) === a) windowA--;
if (s.charCodeAt(start) === b) windowB--;
start++;
}
}
}
}
}
return maxVariance;
}
console.log(largestVarianceSlidingWindow("aababbb")); // Output: 3#include <stdio.h>
#include <string.h>
int largestVarianceSlidingWindow(char *s) {
int maxVariance = 0;
int n = strlen(s);
for (char a = 'a'; a <= 'z'; a++) {
for (char b = 'a'; b <= 'z'; b++) {
if (a == b) continue;
int windowA = 0, windowB = 0, start = 0;
for (int end = 0; end < n; end++) {
if (s[end] == a) windowA++;
if (s[end] == b) windowB++;
if (windowB > 0) {
maxVariance = maxVariance > (windowA - windowB) ?
maxVariance : (windowA - windowB);
}
if (windowA < windowB) {
while (start <= end) {
if (s[start] == a) windowA--;
if (s[start] == b) windowB--;
start++;
}
}
}
}
}
return maxVariance;
}
int main() {
char s[] = "aababbb";
printf("%d\n", largestVarianceSlidingWindow(s)); // Output: 3
return 0;
}using System;
public class Program
{
public static int LargestVarianceSlidingWindow(string s)
{
int maxVariance = 0;
int n = s.Length;
for (char a = 'a'; a <= 'z'; a++)
{
for (char b = 'a'; b <= 'z'; b++)
{
if (a == b) continue;
int windowA = 0, windowB = 0, start = 0;
for (int end = 0; end < n; end++)
{
if (s[end] == a) windowA++;
if (s[end] == b) windowB++;
if (windowB > 0)
{
maxVariance = Math.Max(maxVariance, windowA - windowB);
}
if (windowA < windowB)
{
while (start <= end)
{
if (s[start] == a) windowA--;
if (s[start] == b) windowB--;
start++;
}
}
}
}
}
return maxVariance;
}
public static void Main()
{
Console.WriteLine(LargestVarianceSlidingWindow("aababbb")); // Output: 3
}
}Python's sliding window wraps character evaluations in a way that allows for precise selection of the optimal variance, performing live frequency calculations and window adjustments.
Intelligently maintaining an O(n) temporal profile with limited memory needs (O(1) space), the solution excels in operational brevity.
Approach 3: Enumeration + Dynamic Programming
Since the character set only contains lowercase letters, we can consider enumerating the most frequent character a and the least frequent character b. For a substring, the difference in the number of occurrences of these two characters is the variance of the substring.
Specifically, we use a double loop to enumerate a and b. We use f[0] to record the number of consecutive occurrences of character a ending at the current character, and f[1] to record the variance of the substring ending at the current character and containing both a and b. We iterate to find the maximum value of f[1].
The recurrence formula is as follows:
- If the current character is
a, then bothf[0]andf[1]are incremented by1; - If the current character is
b, thenf[1] = max(f[1] - 1, f[0] - 1), andf[0] = 0; - Otherwise, no need to consider.
Note that initially setting f[1] to a negative maximum value ensures that updating the answer is valid.
The time complexity is O(n times |\Sigma|^2), where n is the length of the string, and |\Sigma| is the size of the character set. The space complexity is O(1).
function largestVariance(s: string): number {
const n: number = s.length;
let ans: number = 0;
for (let a = 97; a <= 122; ++a) {
for (let b = 97; b <= 122; ++b) {
if (a === b) {
continue;
}
const f: number[] = [0, -n];
for (let i = 0; i < n; ++i) {
if (s.charCodeAt(i) === a) {
f[0]++;
f[1]++;
} else if (s.charCodeAt(i) === b) {
f[1] = Math.max(f[0] - 1, f[1] - 1);
f[0] = 0;
}
ans = Math.max(ans, f[1]);
}
}
}
return ans;
}func largestVariance(s string) int {
ans, n := 0, len(s)
for a := 'a'; a <= 'z'; a++ {
for b := 'a'; b <= 'z'; b++ {
if a == b {
continue
}
f := [2]int{0, -n}
for _, c := range 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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Kadane's Algorithm for Character Pair | The time complexity is O(n), driven by pairwise evaluations while efficiently iterating through characters. The space complexity is O(1) for constant space usage. |
| Sliding Window Technique | Intelligently maintaining an O(n) temporal profile with limited memory needs (O(1) space), the solution excels in operational brevity. |
| Enumeration + Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Character Pair Enumeration (Conceptual Brute) | O(26² · n²) | O(1) | Useful for understanding the idea of checking variance for each character pair. |
| Kadane's Algorithm for Character Pair | O(26² · n) | O(1) | Optimal solution. Best for interviews and large inputs. |
| Sliding Window Technique | O(26² · n) | O(1) | Alternative implementation if you prefer window boundaries and frequency counters. |
Frequently asked questions
Is Substring With Largest Variance easy or hard?
Substring With Largest Variance is classified as a Hard problem on LeetCode. The challenge comes from recognizing that variance depends on two characters and converting the problem into a maximum subarray variant. Once that reduction is clear, the Kadane-based solution becomes straightforward to implement.
Substring With Largest Variance Python/Java solution
Python and Java implementations follow the same idea: iterate over all ordered character pairs and apply a modified Kadane scan. Maintain counts of both characters and reset the running score when it becomes negative while ensuring the second character still appears later. The logic is identical across C++, Java, Python, and JavaScript.
How to solve Substring With Largest Variance in O(n)?
Strictly speaking, the algorithm runs O(26^2 · n), but because the alphabet size is constant (26), it is effectively linear. For each ordered character pair (a, b), run a modified Kadane’s algorithm where 'a' contributes +1 and 'b' contributes -1. Reset the running sum when it becomes negative while ensuring at least one 'b' remains ahead.
What is the best approach for Substring With Largest Variance?
The most efficient approach uses Kadane's algorithm applied to every ordered pair of characters. Treat one character as +1 and the other as -1, then run a modified maximum subarray scan across the string. This finds the maximum difference while ensuring both characters appear in the substring. The overall complexity is O(26^2 · n) time and O(1) space.
Is Substring With Largest Variance asked at Google/Amazon/Meta?
Substring With Largest Variance is a known hard-level interview problem and has appeared in interviews at large tech companies including Google and Meta. It tests string processing, dynamic programming intuition, and the ability to adapt Kadane’s algorithm to non-numeric sequences.
What data structure is used in Substring With Largest Variance?
The solution mainly relies on counters and iteration over the string rather than complex data structures. The algorithm uses frequency tracking and dynamic score updates similar to Kadane’s algorithm. Conceptually it combines array traversal with dynamic programming state transitions.
What is the time complexity of Substring With Largest Variance?
The optimal solution runs in O(26^2 · n) time, where n is the length of the string. For each pair of lowercase characters, the algorithm performs a single linear scan using a Kadane-style dynamic programming update. Since the alphabet size is fixed, the runtime behaves close to O(n) in practice.