Substring With Largest Variance - Video Solutions

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.