Problem Description

You are given a string s containing only lowercase English letters.

Your goal is to find the maximum difference between the frequencies of two characters in the string, where:

• The first character (a₁) must appear an odd number of times in the string
• The second character (a₂) must appear an even number of times in the string

The difference is calculated as: diff = freq(a₁) - freq(a₂)

You need to return the maximum possible value of this difference.

For example, if you have a string where:

• Character 'x' appears 5 times (odd frequency)
• Character 'y' appears 2 times (even frequency)
• Character 'z' appears 4 times (even frequency)

You would compare:

• 5 - 2 = 3 (using 'x' with odd frequency 5 and 'y' with even frequency 2)
• 5 - 4 = 1 (using 'x' with odd frequency 5 and 'z' with even frequency 4)

The maximum difference would be 3.

To maximize the difference, you want to find:

• The character with the highest odd frequency for a₁
• The character with the lowest even frequency for a₂

Intuition

To maximize the difference freq(a₁) - freq(a₂), we need to make the first term as large as possible and the second term as small as possible.

Since a₁ must have an odd frequency and a₂ must have an even frequency, we need to:

1. Find the character with the maximum odd frequency to use as a₁
2. Find the character with the minimum even frequency to use as a₂

This gives us the largest possible positive difference.

The key insight is that we don't need to consider all possible pairs of characters - we only need to track two values:

• The largest odd frequency across all characters
• The smallest even frequency across all characters

Why? Because for any difference calculation:

• Using any odd frequency smaller than the maximum would give us a smaller result
• Using any even frequency larger than the minimum would also give us a smaller result

Therefore, the algorithm becomes straightforward:

1. Count the frequency of each character in the string
2. Iterate through all frequencies:
   • If a frequency is odd, update our maximum odd frequency
   • If a frequency is even, update our minimum even frequency
3. Return the difference between the maximum odd and minimum even frequencies

This greedy approach guarantees we find the maximum possible difference in a single pass through the frequency counts.

Solution Approach

The solution uses a counting approach with the following steps:

1. Count Character Frequencies: Use Python's Counter from the collections module to create a hash table cnt that stores the frequency of each character in the string s. This gives us a dictionary where keys are characters and values are their occurrence counts.

2. Initialize Variables:

   • Set a = 0 to track the maximum odd frequency (initialized to 0 as the minimum possible odd frequency would be 1)
   • Set b = inf (infinity) to track the minimum even frequency (initialized to infinity so any even frequency we find will be smaller)

3. Find Maximum Odd and Minimum Even Frequencies: Iterate through all frequency values in cnt.values():

   • For each frequency v:
     • If v % 2 == 1 (odd frequency): Update a = max(a, v) to keep the maximum odd frequency
     • If v % 2 == 0 (even frequency): Update b = min(b, v) to keep the minimum even frequency

4. Return the Difference: Calculate and return a - b, which represents the maximum difference between an odd frequency character and an even frequency character.

The time complexity is O(n) where n is the length of the string (for counting) plus O(26) for iterating through at most 26 different character frequencies (since we only have lowercase English letters), giving us O(n) overall.

The space complexity is O(1) since we store at most 26 character counts in our hash table, which is constant space.

Example Walkthrough

Let's walk through the solution with the string s = "aabbbc".

Step 1: Count Character Frequencies Using Counter, we get:

• 'a': 2 occurrences
• 'b': 3 occurrences
• 'c': 1 occurrence

Step 2: Initialize Variables

• a = 0 (to track maximum odd frequency)
• b = inf (to track minimum even frequency)

Step 3: Find Maximum Odd and Minimum Even Frequencies

Iterate through each frequency:

• Frequency of 'a' = 2:

  • 2 % 2 == 0 (even), so update b = min(inf, 2) = 2
  • Current state: a = 0, b = 2

• Frequency of 'b' = 3:

  • 3 % 2 == 1 (odd), so update a = max(0, 3) = 3
  • Current state: a = 3, b = 2

• Frequency of 'c' = 1:

  • 1 % 2 == 1 (odd), so update a = max(3, 1) = 3
  • Current state: a = 3, b = 2

Step 4: Return the Difference Calculate a - b = 3 - 2 = 1

The maximum difference is 1, achieved by choosing:

• Character 'b' with odd frequency 3
• Character 'a' with even frequency 2

This gives us the optimal difference of 3 - 2 = 1.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the Counter(s) operation iterates through each character in the string once to count the frequency of each character. The subsequent loop through cnt.values() iterates through at most |Σ| values (the number of unique characters), which is bounded by a constant in this case.

The space complexity is O(|Σ|), where Σ is the character set. The Counter object stores at most |Σ| key-value pairs, one for each unique character in the string. Since the problem deals with lowercase English letters, |Σ| = 26, making the space complexity effectively O(26) = O(1) constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Cases Where No Valid Pair Exists

The most critical pitfall in this solution is failing to handle edge cases where either:

• There are no characters with odd frequencies in the string
• There are no characters with even frequencies in the string

Why this is problematic:

• If there are no odd frequencies, max_odd_freq remains 0
• If there are no even frequencies, min_even_freq remains inf
• The result 0 - inf = -inf or 0 - min_even would be invalid or incorrect

Example problematic inputs:

• s = "aabbcc" - all characters have even frequencies (2 each)
• s = "abc" - all characters have odd frequencies (1 each)

2. Solution to the Pitfall

Add validation to check if valid odd and even frequencies exist:

from collections import Counter
from math import inf

class Solution:
    def maxDifference(self, s: str) -> int:
        # Count frequency of each character in the string
        char_frequency = Counter(s)
      
        # Initialize variables to track max odd and min even frequencies
        max_odd_freq = -inf  # Changed from 0 to -inf for consistency
        min_even_freq = inf
      
        # Iterate through all character frequencies
        for freq in char_frequency.values():
            if freq % 2 == 1:  # Check if frequency is odd
                max_odd_freq = max(max_odd_freq, freq)
            else:  # Frequency is even
                min_even_freq = min(min_even_freq, freq)
      
        # Check if we found both odd and even frequencies
        if max_odd_freq == -inf or min_even_freq == inf:
            # Return appropriate value based on problem requirements
            # This could be 0, -1, or raise an exception
            return -1  # or handle according to problem specification
      
        # Return the difference between max odd and min even frequencies
        return max_odd_freq - min_even_freq

3. Alternative Robust Approach

Collect odd and even frequencies separately, then check if both lists are non-empty:

from collections import Counter

class Solution:
    def maxDifference(self, s: str) -> int:
        char_frequency = Counter(s)
      
        odd_frequencies = []
        even_frequencies = []
      
        for freq in char_frequency.values():
            if freq % 2 == 1:
                odd_frequencies.append(freq)
            else:
                even_frequencies.append(freq)
      
        # Check if we have both odd and even frequencies
        if not odd_frequencies or not even_frequencies:
            return -1  # or handle as per problem requirements
      
        return max(odd_frequencies) - min(even_frequencies)

This approach makes the logic clearer and explicitly handles the edge cases where no valid character pair exists.