Maximum Difference Between Even and Odd Frequency I

main.md

Question

Approach

To solve this, I first count the frequency of each character in the string using a frequency map. Then, I look for characters that have odd frequencies and track the maximum among them, since I'm trying to maximize the result. Simultaneously, I look for characters that have even frequencies and track the minimum among them, because subtracting a smaller even count gives a larger difference. Finally, I return the difference between the maximum odd frequency and the minimum even frequency.

Implementation

class Solution:
    def maxDifference(self, s: str) -> int:
        freq = Counter(s)
        max_odd = float('-inf')
        min_even = float('inf')
        
        for count in freq.values():
            if count % 2 == 1:
                max_odd = max(max_odd, count)
            else:
                min_even = min(min_even, count)
        
        return max_odd - min_even

Complexities

• Time: O(n)
• Space: O(1)