Maximum Difference Between Even and Odd Frequency I - Solution & Explanation

Problem Overview: You are given a string and need to compare character frequencies. The goal is to choose one character with an odd frequency and another with an even frequency, then maximize the difference oddFreq - evenFreq. If no valid pair exists, the result is typically -1.

Approach 1: Brute Force Frequency Comparison (O(n + k^2) time, O(k) space)

Start by computing the frequency of each character in the string using a map or array. After collecting all counts, separate them into two groups: characters with odd frequencies and characters with even frequencies. Compare every odd frequency with every even frequency and track the maximum difference. The complexity comes from pairwise comparisons across the two groups. This works because the number of unique characters k is small, but it is still unnecessary work when the optimal values can be derived directly.

Approach 2: Counting + Greedy Extremes (O(n + k) time, O(k) space)

The optimal approach relies on a simple observation: the maximum value of oddFreq - evenFreq will always come from the largest odd frequency and the smallest even frequency. First count character frequencies using a hash map or fixed-size array (typical for lowercase strings). Then iterate through the counts once to track two values: maxOdd and minEven. If both exist, compute maxOdd - minEven. If either group is missing, no valid pair can be formed.

This method reduces the problem to a single counting pass followed by a scan over the frequency values. The algorithm uses constant extra work per character and avoids any nested comparisons. Counting problems like this commonly appear in string interviews and are best handled with structures from hash tables or simple arrays.

The approach also highlights a common interview pattern: reduce a comparison problem into tracking extreme values during iteration. Instead of storing and comparing every candidate pair, maintain the best odd and even candidates while scanning.

Recommended for interviews: The counting approach is the expected solution. Interviewers want to see you quickly build a frequency map (a standard string technique) and reason about extremes rather than brute-force comparisons. Mentioning the brute-force idea first shows understanding, but implementing the counting optimization demonstrates stronger problem-solving skills.