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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Difference Between Even and Odd Frequency I

Number: 3753

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a string s consisting of lowercase English letters, find the maximum difference between the frequency of any two characters such that one character has an even frequency and the other has an odd frequency. The difference is computed as (odd frequency - even frequency). It is guaranteed that there is at least one character with an odd frequency and one with an even frequency.

Key Insights

  • Use a hash table (or dictionary) to count the frequency of each character.
  • Group the frequencies into odd and even buckets.
  • Iterate over all pairs of odd and even frequencies and compute the difference (odd - even).
  • Track the maximum difference throughout the iteration.

Space and Time Complexity

Time Complexity: O(n + C^2), where n is the length of the string and C is the number of distinct characters (at most 26).
Space Complexity: O(C) for storing character frequencies.

Solution

We first count the frequency of each character using a hash table. Then, we segregate the frequencies into two lists: one for odd frequencies and one for even frequencies. By comparing every odd frequency with every even frequency, we compute the difference (odd - even) and update the maximum difference we encounter. Given the constraint that there are at most 26 different characters, the nested iteration over pairs is efficient.

Code Solutions

# Function to compute the maximum difference between odd frequency and even frequency characters.
def maxDifference(s: str) -> int:
    freq = {}
    # Count the frequency of each character in the string.
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    
    odd_freq = []
    even_freq = []
    # Separate frequencies into odd and even buckets.
    for count in freq.values():
        if count % 2 == 0:
            even_freq.append(count)
        else:
            odd_freq.append(count)
    
    max_diff = float('-inf')
    # Compute the maximum difference: odd frequency minus even frequency.
    for odd in odd_freq:
        for even in even_freq:
            max_diff = max(max_diff, odd - even)
    
    return max_diff

# Example usage:
print(maxDifference("aaaaabbc"))  # Expected output: 3
← Back to All Questions