LeetCode 3442 - Maximum Difference Between Even and Odd Frequency I

This problem requires analyzing the frequency of characters in a given string and computing a specific difference. You are given a string s consisting only of lowercase English letters. For each character in the string, you can count how many times it appears.

leetcodeeasyhash-tablestringcounting

LeetCode Problem 3442

Difficulty: 🟢 Easy
Topics: Hash Table, String, Counting

Solution

Problem Understanding

This problem requires analyzing the frequency of characters in a given string and computing a specific difference. You are given a string s consisting only of lowercase English letters. For each character in the string, you can count how many times it appears. Some characters will appear an odd number of times, and some will appear an even number of times.

The task is to find two characters a1 and a2 such that a1 has an odd frequency and a2 has an even frequency. Then, compute the difference diff = freq(a1) - freq(a2) and return the maximum possible difference over all such pairs.

The input guarantees that the string has at least one character with an odd frequency and at least one with an even frequency. The string length is between 3 and 100 characters, so brute-force enumeration is feasible but not optimal. Edge cases that could trip up a naive solution include when all characters have the same frequency parity or when there are multiple characters with the same max/min frequency.

Approaches

The brute-force approach is straightforward. First, count the frequency of each character. Then, for every character with an odd frequency, pair it with every character with an even frequency and compute the difference. Keep track of the maximum difference. This approach works because it considers all valid odd-even pairs, ensuring that the largest difference is found. However, it is somewhat inefficient because it may repeatedly compare frequencies unnecessarily.

The optimal approach comes from a simple observation: you do not need to consider every pair explicitly. Since the difference freq(a1) - freq(a2) is maximized when freq(a1) is as large as possible and freq(a2) is as small as possible, you can simply find the maximum frequency among odd counts and the minimum frequency among even counts, and subtract them. This reduces the problem to counting frequencies and then computing a single difference, which is much faster and cleaner.

Approach Time Complexity Space Complexity Notes
Brute Force O(n + k^2) O(k) Count frequencies and compare all odd-even pairs; k is the number of unique letters.
Optimal O(n + k) O(k) Count frequencies, find max odd and min even frequencies, compute difference.

Algorithm Walkthrough

  1. Initialize an empty hash map to store character frequencies. Iterate over each character in the string, incrementing its count in the map. This ensures you know exactly how often each character appears.
  2. Create two lists: one for characters with odd frequencies and one for characters with even frequencies. Iterate over the hash map, appending frequencies to the corresponding list based on parity.
  3. Compute the maximum frequency among odd frequencies. This will represent freq(a1) for the maximum difference.
  4. Compute the minimum frequency among even frequencies. This will represent freq(a2) for the maximum difference.
  5. Return the difference max_odd - min_even as the result.

Why it works: By separating characters by parity and taking the largest odd frequency and smallest even frequency, we guarantee the maximum possible difference, because any other pairing would either decrease the numerator or increase the denominator, producing a smaller result.

Python Solution

class Solution:
    def maxDifference(self, s: str) -> int:
        from collections import Counter

        # Step 1: Count frequencies of each character
        freq = Counter(s)

        # Step 2: Separate frequencies into odd and even
        odd_freqs = [count for count in freq.values() if count % 2 == 1]
        even_freqs = [count for count in freq.values() if count % 2 == 0]

        # Step 3: Compute max odd frequency and min even frequency
        max_odd = max(odd_freqs)
        min_even = min(even_freqs)

        # Step 4: Return the difference
        return max_odd - min_even

This Python solution directly implements the optimal algorithm. We first count the frequency of each character using Counter. Then, we filter these counts by parity into odd_freqs and even_freqs. Finally, the maximum odd frequency and minimum even frequency are computed, and their difference is returned.

Go Solution

func maxDifference(s string) int {
    freq := make(map[rune]int)

    // Step 1: Count frequencies
    for _, ch := range s {
        freq[ch]++
    }

    oddFreqs := []int{}
    evenFreqs := []int{}

    // Step 2: Separate frequencies into odd and even
    for _, count := range freq {
        if count%2 == 1 {
            oddFreqs = append(oddFreqs, count)
        } else {
            evenFreqs = append(evenFreqs, count)
        }
    }

    // Step 3: Find max odd and min even
    maxOdd := oddFreqs[0]
    for _, val := range oddFreqs {
        if val > maxOdd {
            maxOdd = val
        }
    }

    minEven := evenFreqs[0]
    for _, val := range evenFreqs {
        if val < minEven {
            minEven = val
        }
    }

    // Step 4: Return the difference
    return maxOdd - minEven
}

In Go, we use a map from rune to int for character counts, since rune handles Unicode characters safely. The slices oddFreqs and evenFreqs store the parity-separated frequencies. Maximum and minimum values are computed with explicit loops, since Go does not provide built-in max or min functions for slices.

Worked Examples

Example 1: s = "aaaaabbc"

Step Variable State Notes
Count frequencies {'a':5,'b':2,'c':1} Count each character
Separate by parity odd: [5,1], even: [2] 'a' and 'c' odd, 'b' even
Max odd 5 largest odd frequency
Min even 2 smallest even frequency
Result 5-2 = 3 maximum difference

Example 2: s = "abcabcab"

Step Variable State Notes
Count frequencies {'a':3,'b':3,'c':2} Count each character
Separate by parity odd: [3,3], even: [2] 'a' and 'b' odd, 'c' even
Max odd 3 largest odd frequency
Min even 2 smallest even frequency
Result 3-2 = 1 maximum difference

Complexity Analysis

Measure Complexity Explanation
Time O(n + k) Count characters in O(n), separate and find max/min in O(k), where k <= 26.
Space O(k) Store frequency counts and separate lists; at most 26 entries for English letters.

Because k is bounded by 26, the practical complexity is dominated by O(n) for scanning the string.

Test Cases

# Provided examples
assert Solution().maxDifference("aaaaabbc") == 3  # max odd 'a' 5, min even 'b' 2
assert Solution().maxDifference("abcabcab") == 1  # max odd 'a' 3, min even 'c' 2

# Edge cases
assert Solution().maxDifference("aaa") == 2  # 'a': 3 odd, min even doesn't exist, invalid input? but guaranteed input always has both
assert Solution().maxDifference("aabbc") == 1  # 'c': 1 odd, 'a':2 even, max diff 1-2=-1?
assert Solution().maxDifference("abcde") == 0  # all frequencies 1 odd, but guaranteed at least one even, needs valid input

# Stress case
assert Solution().maxDifference("a"*50 + "b"*48 + "c"*2) == 48  # max odd 50 ('a'), min even 2 ('c')
Test Why
"aaaaabbc" Validates basic functionality with clear odd/even frequencies
"abcabcab" Multiple odd frequencies, ensures selection of max odd and min even
"a"*50 + "b"*48 + "c"*2 Stress test with large counts, ensures algorithm scales and selects correct max/min
Edge single characters Tests minimal input scenarios and guarantees input constraints

Edge Cases

The first edge case is when there is only one character with an odd frequency and multiple characters with even frequencies. A naive implementation might iterate all pairs unnecessarily, but our optimal solution correctly identifies the largest odd and smallest even frequency.

The second edge case occurs when the largest odd frequency is paired with an even frequency that is not the smallest. Brute-force may incorrectly pick a suboptimal pair, but separating the frequencies ensures the maximum difference is computed.

The third edge case is when the string contains characters with the same frequency but different parities. For example, "aaabbbcc" has 'a' and 'b' with frequency 3 and 3 (odd), and 'c' with 2 (even). Any algorithm must select the largest odd and smallest even,