Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The desired difference is an odd frequency minus a positive even frequency. These choices are independent, so maximize the first term and minimize the second. A character cannot belong to both categories, which also guarantees the selected characters are different.

Approach

Count the occurrences of each character in a frequency map. Scan the map's positive counts, retaining the largest odd count and the smallest even count. Return their difference.

Only characters that actually occur are considered; a missing character's zero frequency must not be used as the even-frequency choice. The problem guarantees that both required frequency types exist. The result may be negative when every odd frequency is smaller than every positive even frequency, so it should not be clamped to zero.

class Solution:
    def maxDifference(self, s: str) -> int:
        map = defaultdict(int)
        for c in s:
            map[c] += 1

        a1, a2 = 0, float('inf')

        for k in map:
            if map[k] % 2:
                a1 = max(a1, map[k])
            else:
                a2 = min(a2, map[k])

        return a1 - a2

Complexity analysis

Let n = s.length and u be the number of distinct characters. Time: O(n + u). Auxiliary space: O(u).