Skip to main content
Talentd

Substring With Largest Variance - Solution & Explanation

HardArrayDynamic Programming19 min readAsked at: Amazon
Practice this problem

Problem Statement

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.

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.

The solution involves iterating over all possible pairs of characters (a, b). For each pair, we calculate the difference in frequency counts using a variation of Kadane's algorithm approach to determine the maximum variance for that pair. The balance is reset when frequency of 'b' exceeds 'a', avoiding any negative variance.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(26^2 * n) = O(n), where n is the length of the string, due to iterating over each character pair and traversing the string. The space complexity is O(1) because we use only a fixed amount of extra space.

Try this approach in the editor →

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.

In this C solution using the sliding window technique, we maintain a dynamic window while iterating over the string. The window adjusts dynamically to keep the variance optimal, expanding and contracting based on character balance.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity is O(n) due to efficient window management, spanning the string with a single pass, and space complexity veins at O(1) for predictable and limited use.

Try this approach in the editor →

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:

  1. If the current character is a, then both f[0] and f[1] are incremented by 1;
  2. If the current character is b, then f[1] = max(f[1] - 1, f[0] - 1), and f[0] = 0;
  3. 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Kadane's Algorithm for Character Pair

The time complexity is O(26^2 * n) = O(n), where n is the length of the string, due to iterating over each character pair and traversing the string. The space complexity is O(1) because we use only a fixed amount of extra space.

Sliding Window Technique

Time complexity is O(n) due to efficient window management, spanning the string with a single pass, and space complexity veins at O(1) for predictable and limited use.

Enumeration + Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 PairO(26² · n)O(1)Optimal solution. Best for interviews and large inputs.
Sliding Window TechniqueO(26² · n)O(1)Alternative implementation if you prefer window boundaries and frequency counters.

Video Solution

Substring With Largest Variance | 2272 LeetCode | Maths | Leetcode Biweekly Contest 78 • CodeWithSunny • 12,733 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Substring With Largest Variance with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Subarray