Maximum Difference Between Even and Odd Frequency I

How it works

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.

Steps

1. Count the frequency of each character in the string.
2. Track oddMax as the largest frequency that is odd.
3. Track evenMin as the smallest frequency that is even (and greater than 0).
4. Return oddMax - evenMin.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) since we have at most 26 different characters.

Things to watch for

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.

from collections import Counter

class Solution:
    def maxDifference(self, s: str) -> int:
        count = Counter(s)
        oddMax, evenMin = 0, len(s)

        for cnt in count.values():
            if cnt & 1:
                oddMax = max(oddMax, cnt)
            else:
                evenMin = min(evenMin, cnt)

        return oddMax - evenMin

class Solution {
public:
    int maxDifference(string s) {
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }

        int oddMax = 0, evenMin = s.length();
        for (int c : count) {
            if (c & 1) {
                oddMax = max(oddMax, c);
            } else if (c > 0) {
                evenMin = min(evenMin, c);
            }
        }

        return oddMax - evenMin;
    }
};