Substring With Largest Variance

Hard
1629.

Substring With Largest Variance

Substring With Largest Variance is a hard coding problem on arrays and dynamic programming, asked in Amazon and Microsoft interviews.

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^4
  • s consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var largestVariance = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • s consists of lowercase English letters

Hints for Substring With Largest Variance

  1. Hint 1

    The answer is achieved by some pair of letters: a the most frequent and b the least frequent in the best substring. There are only 26 * 25 ordered pairs.

  2. Hint 2

    For a fixed pair, map a to +1, b to -1 and every other letter to 0. The variance of a substring is its sum — but only if the substring contains at least one b.

  3. 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 of b exceeds a only if another b is 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

  1. For every ordered pair (a, b) of distinct letters that both occur in s:
  2. Scan s keeping ca and cb (counts in the current window) and restB (occurrences of b not yet scanned).
  3. On a, ca++; on b, cb++ and restB--. Whenever cb > 0, update the answer with ca - cb.
  4. If ca < cb and restB > 0, reset both counts to 0 — a window starting later can do better and will still find a b.
  5. 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 b does not count: "aaaa" scores 0, not 4.
  • Resetting whenever ca < cb loses windows like "baaa": keep the b when 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 best

Java

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