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

1. Count the frequency of each character in the string.
2. Iterate through all pairs of frequencies where one is odd and one is even.
3. For each valid pair, compute odd - even and track the maximum.
4. Return the maximum difference found.

class Solution:
    def maxDifference(self, s: str) -> int:
        count = Counter(s)
        res = float("-inf")

        for odd in count.values():
            if odd % 2 == 0: continue
            for even in count.values():
                if even % 2 == 1: continue
                res = max(res, odd - even)

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ since we have at most $26$ 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

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.

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

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ since we have at most $26$ 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.