Maximum Difference Between Even and Odd Frequency I

Difficulty: Easy | Acceptance: 60.70% | Paid: No Topics: Hash Table, String, Counting

You are given a string word. You need to calculate the difference between the sum of frequencies of characters that appear an even number of times and the sum of frequencies of characters that appear an odd number of times.

Return the maximum possible difference.

• Examples
• Constraints
• Hash Map Counting
• Array Counting
• Sorting Approach

Examples

Example 1

Input:

s = "aaaaabbc"

Output:

3

Explanation: The character ‘a’ has an odd frequency of 5, and ‘b’ has an even frequency of 2.

The maximum difference is 5 - 2 = 3.

Example 2

Input:

s = "abcabcab"

Output:

1

Explanation: The character ‘a’ has an odd frequency of 3, and ‘c’ has an even frequency of 2.

The maximum difference is 3 - 2 = 1.

Constraints

- 3 <= s.length <= 100
- s consists only of lowercase English letters.
- s contains at least one character with an odd frequency and one with an even frequency.

Hash Map Counting

Intuition Use a hash map to count the frequency of each character, then iterate through the map to separate even and odd frequencies.

Steps

• Create a hash map to store character frequencies
• Iterate through the string and count each character
• Iterate through the hash map, adding frequencies to even or odd sum based on parity
• Return the absolute difference

class Solution:
    def maxDifference(self, word: str) -> int:
        freq = {}
        for c in word:
            freq[c] = freq.get(c, 0) + 1
        
        even_sum = 0
        odd_sum = 0
        for count in freq.values():
            if count % 2 == 0:
                even_sum += count
            else:
                odd_sum += count
        
        return abs(even_sum - odd_sum)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(k) where k is the number of unique characters (at most 26 for lowercase letters)
• Notes: Simple and intuitive approach using hash map for counting

Array Counting

Intuition Since the input only contains lowercase English letters, we can use a fixed-size array of 26 elements for counting, which is more efficient than a hash map.

Steps

• Create an array of size 26 initialized to 0
• Iterate through the string, incrementing the count for each character
• Iterate through the array, adding frequencies to even or odd sum based on parity
• Return the absolute difference

class Solution:
    def maxDifference(self, word: str) -> int:
        freq = [0] * 26
        for c in word:
            freq[ord(c) - ord('a')] += 1
        
        even_sum = 0
        odd_sum = 0
        for count in freq:
            if count % 2 == 0:
                even_sum += count
            else:
                odd_sum += count
        
        return abs(even_sum - odd_sum)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) since the array size is fixed at 26
• Notes: More space-efficient than hash map for lowercase letters only

Sorting Approach

Intuition Sort the string so identical characters are adjacent, then count consecutive characters to find frequencies.

Steps

• Convert the string to a character array and sort it
• Iterate through the sorted array, counting consecutive identical characters
• For each group of identical characters, add the frequency to even or odd sum based on parity
• Return the absolute difference

class Solution:
    def maxDifference(self, word: str) -> int:
        chars = sorted(word)
        
        even_sum = 0
        odd_sum = 0
        i = 0
        n = len(chars)
        
        while i < n:
            count = 1
            while i + count < n and chars[i + count] == chars[i]:
                count += 1
            
            if count % 2 == 0:
                even_sum += count
            else:
                odd_sum += count
            
            i += count
        
        return abs(even_sum - odd_sum)

Complexity

• Time: O(n log n) due to sorting
• Space: O(n) for the character array (or O(1) if sorting in place)
• Notes: Less efficient than counting approaches due to sorting overhead