💬 Discord
Sign In
NeetCode #47LC-3442EasyArrays & Hashing
← Back to All Problems

#47 · #3442 · Maximum Difference Between Even and Odd Frequency I(奇偶频次间的最大差值 I)

📌 Problem Statement & Constraints

Given a string s, find the maximum difference between the frequency of a character appearing an even number of times and the frequency of a character appearing an odd number of times. Return max(even_freq - odd_freq), or 0 if no such pair exists. Constraints: 3 <= s.length <= 100.

💡 Core Algorithmic Approaches

  1. Compute the frequency of every character with Counter.
  2. Partition the frequencies into even ones and odd ones.
  3. If either group is empty, no valid pair exists, so return 0.
  4. Otherwise the maximum difference uses the largest even frequency and the smallest odd frequency.
  5. Note that a frequency of 0 never appears in the counter, so even frequencies are always at least 2 -- no need to filter zeros.

💻 Benchmark Python3 Implementation

class Solution:
    def maxDifference(self, s: str) -> int:
        from collections import Counter
        freq = Counter(s).values()
        even = [f for f in freq if f % 2 == 0]
        odd = [f for f in freq if f % 2 == 1]
        if not even or not odd:            # need at least one of each
            return 0
        return max(even) - min(odd)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + k): O(n) to count, then a constant-size scan over the at most 26 distinct characters.
💾 Space Complexity
O(k) for the counter and the two lists, with k <= 26.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the empty-group check: if every character occurs an odd number of times, there is no even frequency and the answer is 0, not a negative number.
  • Using max(odd) - min(even): the sign is reversed; the even frequency comes first and must be the larger one.
  • Including zero frequencies: characters absent from the string are not in the counter, so zeros never enter the lists -- but if you iterate over a fixed 26-letter alphabet, they would, and 0 is even, which would corrupt the answer.
  • Assuming the answer is always positive: it can be 0, and the problem allows returning 0.