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.
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; }}Video 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.