Substring With Largest Variance
HardPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to check every single possibility. We can generate all substrings of the input string s. For each of these substrings, we then calculate its variance. To calculate the variance of a substring, we find the frequency of all characters within it and then compute the difference in counts for every possible pair of characters, keeping track of the maximum difference found.
Algorithm
- Generate all possible substrings of the input string
s. - For each substring:
a. Create a frequency map (e.g., an array of size 26) to count the occurrences of each character in the substring.
b. Iterate through all possible pairs of characters (
char1,char2). c. Calculate the variance for the pair:frequency[char1] - frequency[char2]. d. Keep track of the maximum variance found across all substrings and all character pairs. - Return the overall maximum variance.
Walkthrough
This method involves three nested loops. The outer two loops define the start and end points of a substring. The third, inner loop (or equivalent operation) iterates through the substring to build a frequency count of its characters. After counting, two more loops iterate through all 26*26 pairs of characters to find the maximum difference in frequencies.
class Solution { public int largestVariance(String s) { int maxVariance = 0; int n = s.length(); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { String sub = s.substring(i, j + 1); int[] freq = new int[26]; for (char c : sub.toCharArray()) { freq[c - 'a']++; } for (int c1 = 0; c1 < 26; c1++) { for (int c2 = 0; c2 < 26; c2++) { if (freq[c1] > 0 && freq[c2] > 0) { maxVariance = Math.max(maxVariance, freq[c1] - freq[c2]); } } } } } return maxVariance; }}Note: The condition freq[c1] > 0 && freq[c2] > 0 ensures both characters are present in the substring. If the problem allows for a character not present (count 0), this check can be simplified.
Complexity
Time
O(N³), where N is the length of the string. There are O(N²) substrings. For each substring of length L, it takes O(L) to build the frequency map. Since L can be up to N, this results in an O(N³) complexity. The final loops over character pairs are constant time (26*26).
Space
O(1), as the frequency map has a constant size of 26.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient and will time out for the given constraints.
We can optimize the brute-force approach by improving how we calculate character frequencies. Instead of recounting characters for every substring, we can iterate through all possible start points. For each start point, we extend the substring one character at a time, updating the frequency map incrementally. This avoids the redundant counting of the previous approach.
Algorithm
- Iterate through all possible starting positions
iof a substring. - For each
i, start a second loop for the ending positionjfromito the end of the string. - Maintain a frequency map for the current substring
s.substring(i, j+1). Instead of rebuilding it for each substring, initialize it at the start of the outer loop and update it by one character asjincrements. - For each substring defined by
(i, j), iterate through all character pairs to find the maximum frequency difference and update the global maximum variance. - Return the global maximum variance.
Walkthrough
This approach reduces the complexity of calculating frequencies. For a fixed starting point i, as we extend the end point j, we only need to account for the new character s.charAt(j). This brings the complexity of handling all substrings starting at i down to O(N). Since we do this for all N possible start points, the total complexity is improved.
class Solution { public int largestVariance(String s) { int maxVariance = 0; int n = s.length(); for (int i = 0; i < n; i++) { int[] freq = new int[26]; for (int j = i; j < n; j++) { freq[s.charAt(j) - 'a']++; // Now freq is for substring s[i..j] for (int c1 = 0; c1 < 26; c1++) { for (int c2 = 0; c2 < 26; c2++) { if (freq[c1] > 0 && freq[c2] > 0) { maxVariance = Math.max(maxVariance, freq[c1] - freq[c2]); } } } } } return maxVariance; }}Complexity
Time
O(N²). The two nested loops for `i` and `j` give O(N²). The inner operations (updating frequency and checking all 26*26 pairs) take constant time.
Space
O(1), for the frequency map.
Trade-offs
Pros
More efficient than the naive brute-force approach.
Cons
Still too slow for the given constraints, likely to result in a Time Limit Exceeded error.
A much more efficient approach is to change the perspective. Instead of iterating through substrings, we iterate through all possible pairs of characters (c1, c2) that could produce the variance. For each fixed pair, we aim to find a substring that maximizes count(c1) - count(c2). This subproblem can be solved in linear time using a modified version of Kadane's algorithm.
Algorithm
- The core idea is to fix the two characters (
c1andc2) for which we want to maximize the count difference (count(c1) - count(c2)). - Iterate through all 26 * 25 possible pairs of distinct characters (
c1as the character with higher frequency,c2with lower). - For each pair, iterate through the string
sto find the maximum variance for just these two characters. This subproblem is equivalent to finding the maximum subarray sum, a problem that can be solved with Kadane's algorithm. - We treat
c1as+1andc2as-1. The challenge is that the substring must contain at least one of each character. - A modified Kadane's algorithm is used. We maintain counts for
c1andc2. Ifcount2becomes greater thancount1, it's detrimental to extend the current substring, so we reset the counts, effectively starting a new substring. - An issue with this reset is that an optimal substring might have a prefix where
count2 > count1. To handle this, the process is run twice for each pair: once on the original string and once on its reverse. This ensures we capture all cases. - The overall maximum variance is the maximum found across all character pairs and both passes (forward and backward).
Walkthrough
For a fixed pair of characters, say major = 'a' and minor = 'b', we want to find a substring with the maximum value of count('a') - count('b'). We can iterate through the string, maintaining a running count for major and minor. Let these be majorCount and minorCount.
The variance is updated whenever we have seen at least one of each character (majorCount > 0 and minorCount > 0). A key part of this modified Kadane's algorithm is the reset condition. If majorCount < minorCount, it's often better to start a new substring, so we reset both counts to zero. However, this greedy reset can fail if the optimal substring has a prefix that meets this condition. For example, in s = "ababbb" and pair ('b', 'a'), the optimal substring is "babbb" (variance 2), but the algorithm might incorrectly reset after processing the prefix "aba".
To solve this, the entire procedure is run twice for each pair: once on the string from left-to-right, and once from right-to-left (by reversing the string). This ensures that no matter how the optimal substring is structured, one of the two passes will find it correctly.
class Solution { public int largestVariance(String s) { int maxVariance = 0; int[] freq = new int[26]; for (char c : s.toCharArray()) { freq[c - 'a']++; } for (char c1 = 'a'; c1 <= 'z'; c1++) { for (char c2 = 'a'; c2 <= 'z'; c2++) { if (c1 == c2 || freq[c1 - 'a'] == 0 || freq[c2 - 'a'] == 0) { continue; } // Run modified Kadane's for this pair maxVariance = Math.max(maxVariance, calculateVarianceForPair(s, c1, c2)); } } return maxVariance; } private int calculateVarianceForPair(String s, char c1, char c2) { int maxVariance = 0; int count1 = 0, count2 = 0; // Run twice, once forward, once backward (by reversing the string) for (int run = 0; run < 2; run++) { count1 = 0; count2 = 0; for (char ch : s.toCharArray()) { if (ch == c1) { count1++; } else if (ch == c2) { count2++; } if (count1 > 0 && count2 > 0) { maxVariance = Math.max(maxVariance, count1 - count2); } if (count1 < count2) { count1 = 0; count2 = 0; } } // Reverse the string for the second run s = new StringBuilder(s).reverse().toString(); } return maxVariance; }}Complexity
Time
O(N). The main loop iterates through all 26*26 pairs of characters, which is a constant factor (C = 26*26). For each pair, we perform a linear scan (O(N)) of the string twice. Thus, the total time complexity is O(C * N), which simplifies to O(N).
Space
O(N) if we consider the space for the reversed string. If the string is reversed in-place or iterated backwards with an index, space complexity can be O(1).
Trade-offs
Pros
Highly efficient and passes within the time limits.
Reduces the problem to a known pattern (Kadane's algorithm).
Cons
The logic for the modified Kadane's algorithm is complex and non-trivial to derive correctly.
Solutions
Solution
class Solution {public int largestVariance(String s) { int n = s.length(); int ans = 0; for (char a = 'a'; a <= 'z'; ++a) { for (char b = 'a'; b <= 'z'; ++b) { if (a == b) { continue; } int[] f = new int[]{0, -n}; for (int i = 0; i < n; ++i) { if (s.charAt(i) == a) { f[0]++; f[1]++; } else if (s.charAt(i) == b) { f[1] = Math.max(f[0] - 1, f[1] - 1); f[0] = 0; } ans = Math.max(ans, f[1]); } } } return ans; }}class Solution { public: int largestVariance ( string s ) { int n = s . size (); int ans = 0 ; for ( char a = 'a' ; a <= 'z' ; ++ a ) { for ( char b = 'a' ; b <= 'z' ; ++ b ) { if ( a == b ) continue ; int f [ 2 ] = { 0 , - n }; for ( char c : 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 ; } };class Solution : def largestVariance ( self , s : str ) -> int : ans = 0 for a , b in permutations ( ascii_lowercase , 2 ): if a == b : continue f = [ 0 , - inf ] for c in s : if c == a : f [ 0 ], f [ 1 ] = f [ 0 ] + 1 , f [ 1 ] + 1 elif c == b : f [ 1 ] = max ( f [ 1 ] - 1 , f [ 0 ] - 1 ) f [ 0 ] = 0 if ans < f [ 1 ]: ans = f [ 1 ] return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.