3442. Maximum Difference Between Even and Odd Frequency I - Explanation

Problem Link

Description

You are given a string s consisting of lowercase English letters.

Your task is to find the maximum difference diff = freq(a1) - freq(a2) between the frequency of characters a1 and a2 in the string such that:

• a1 has an odd frequency in the string.
• a2 has an even frequency in the string.

Return this maximum difference.

Example 1:

Input: s = "aaaaabbc"

Output: 3

Explanation:

• The character 'a' has an odd frequency of 5, and 'b' has an even frequency of 2.
• The maximum difference is 5 - 2 = 3.

Example 2:

Input: s = "abcabcab"

Output: 1

Explanation:

• The character 'a' has an odd frequency of 3, and 'c' has an even frequency of 2.
• The maximum difference is 3 - 2 = 1.

Constraints:

• 3 <= s.length <= 100
• s consists only of lowercase English letters.
• s contains at least one character with an odd frequency and one with an even frequency.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Counting

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)

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.