Prerequisites
Before attempting this problem, you should be comfortable with:
- Hash Maps / Frequency Counting - Counting occurrences of elements using dictionaries or arrays
- Parity (Odd/Even) - Determining whether a number is odd or even using modulo or bitwise operations
1. Counting
Intuition
We want to maximize (frequency of some character with odd count) - (frequency of some character with even count). The straightforward approach is to count how often each character appears, then check all pairs where one has an odd frequency and the other has an even frequency. We take the maximum difference among all valid pairs.
Algorithm
- Count the frequency of each character in the string.
- Iterate through all pairs of frequencies where one is odd and one is even.
- For each valid pair, compute
odd - evenand track the maximum. - Return the maximum difference found.
Time & Space Complexity
- Time complexity:
- Space complexity: since we have at most different characters.
2. Counting (Optimal)
Intuition
Instead of checking all pairs, we can observe that to maximize odd - even, we should pick the largest odd frequency and the smallest even frequency. This gives us the optimal answer in a single pass through the frequency counts.
Algorithm
- Count the frequency of each character in the string.
- Track
oddMaxas the largest frequency that is odd. - Track
evenMinas the smallest frequency that is even (and greater than0). - Return
oddMax - evenMin.
Time & Space Complexity
- Time complexity:
- Space complexity: since we have at most different characters.
Common Pitfalls
Including Zero Frequencies
Characters that do not appear in the string have frequency zero, which is technically even. However, you cannot use a zero-frequency character as the "even frequency" character because it does not exist in the string. Always filter out zero counts when looking for the minimum even frequency.
Swapping Odd and Even in the Difference
The problem asks for (odd frequency) - (even frequency), not the other way around. Maximizing even - odd instead gives the wrong answer. Pay attention to which frequency should be maximized and which should be minimized.