Maximum Difference Between Even and Odd Frequency I
Source: leetcode
Difficulty: Easy
Tags: hash-table, string, counting

You are given a string `s` consisting of lowercase English letters. Your task is to find the **maximum** difference between the frequency of **two** characters in the string such that:


- One of the characters has an **even frequency** in the string.
- The other character has an **odd frequency** in the string.


Return the **maximum** difference, calculated as the frequency of the character with an **odd** frequency **minus** the frequency of the character with an **even** frequency.


 


**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.




C++ solution:
class Solution {
public:
    int maxDifference(string s) {
        vector<int> freq(26, 0);
        for (char c : s) {
            freq[c - 'a']++;
        }
        
        vector<int> evens, odds;
        for (int i = 0; i < 26; ++i) {
            if (freq[i] == 0) continue;
            if (freq[i] % 2 == 0) {
                evens.push_back(freq[i]);
            } else {
                odds.push_back(freq[i]);
            }
        }
        
        int max_odd = *max_element(odds.begin(), odds.end());
        int min_even = *min_element(evens.begin(), evens.end());
        
        return max_odd - min_even;
    }
};

Go solution:
func maxDifference(s string) int {
    freq := make(map[rune]int)
    for _, c := range s {
        freq[c]++
    }
    var evens, odds []int
    for _, v := range freq {
        if v%2 == 0 {
            evens = append(evens, v)
        } else {
            odds = append(odds, v)
        }
    }
    maxOdd := 0
    for _, o := range odds {
        if o > maxOdd {
            maxOdd = o
        }
    }
    minEven := int(^uint(0) >> 1)
    for _, e := range evens {
        if e < minEven {
            minEven = e
        }
    }
    return maxOdd - minEven
}

Java solution:
class Solution {
    public int maxDifference(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        java.util.List<Integer> even = new java.util.ArrayList<>();
        java.util.List<Integer> odd = new java.util.ArrayList<>();
        for (int count : freq) {
            if (count > 0) {
                if (count % 2 == 0) {
                    even.add(count);
                } else {
                    odd.add(count);
                }
            }
        }
        int maxOdd = java.util.Collections.max(odd);
        int minEven = java.util.Collections.min(even);
        return maxOdd - minEven;
    }
}

JavaScript solution:
/**
 * @param {string} s
 * @return {number}
 */
var maxDifference = function(s) {
    const freq = {};
    for (const c of s) {
        freq[c] = (freq[c] || 0) + 1;
    }
    const evens = [];
    const odds = [];
    for (const c in freq) {
        const count = freq[c];
        (count % 2 === 0 ? evens : odds).push(count);
    }
    let maxDiff = -Infinity;
    for (const odd of odds) {
        for (const even of evens) {
            maxDiff = Math.max(maxDiff, odd - even);
        }
    }
    return maxDiff;
};

Python solution:
class Solution:
    def maxDifference(self, s: str) -> int:
        freq = Counter(s)
        even = []
        odd = []
        for v in freq.values():
            if v % 2 == 0:
                even.append(v)
            else:
                odd.append(v)
        max_odd = max(odd)
        min_even = min(even)
        return max_odd - min_even

Ruby solution:
def max_difference(s)
  freq = s.chars.each_with_object(Hash.new(0)) { |c, h| h[c] += 1 }
  even = []
  odd = []
  freq.each_value do |v|
    v.even? ? even << v : odd << v
  end
  max_odd = odd.max
  min_even = even.min
  max_odd - min_even
end