We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Substring With Largest Variance

Difficulty: Hard

Problem Description

Given a string s consisting of lowercase English letters only, return the largest variance possible among all substrings of s. The variance is defined as the largest difference between the number of occurrences of any two characters present in the string.

Key Insights

  • The variance is calculated by considering the counts of two characters in a substring.
  • The maximum variance occurs when one character is significantly more frequent than the other.
  • We can utilize a sliding window approach to explore all pairs of characters in the string.
  • Characters that are not part of the two selected characters can be ignored in the variance calculation.

Space and Time Complexity

Time Complexity: O(26^2 * n) - where n is the length of the string, and we consider all pairs of characters (there are 26 lowercase letters). Space Complexity: O(1) - we only use a fixed amount of space for character counts.

Solution

To solve the problem, we can employ a sliding window technique paired with a frequency count for two selected characters at a time. For each pair of characters, we traverse the string while maintaining their counts. We calculate the variance as we go, ensuring to adjust counts when we encounter characters that are not part of the selected pair. The aim is to maximize the variance over all possible pairs.

Code Solutions

def largestVariance(s: str) -> int:
    max_variance = 0
    unique_chars = set(s)
    
    # Check all pairs of unique characters
    for a in unique_chars:
        for b in unique_chars:
            if a != b:
                count_a = count_b = 0
                has_a = has_b = False
                
                # Sliding window to calculate variance
                for char in s:
                    if char == a:
                        count_a += 1
                        has_a = True
                    elif char == b:
                        count_b += 1
                        has_b = True
                    
                    # Only when we have at least one of each character
                    if has_a and has_b:
                        max_variance = max(max_variance, count_a - count_b)
                    
                    # Reset counts when count_b exceeds count_a
                    if count_b > count_a:
                        count_a = count_b = 0
                        has_a = has_b = False
    
    return max_variance
← Back to All Questions