# Maximum Difference Between Even and Odd Frequency I
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-difference-between-even-and-odd-frequency-i)
Canonical: https://scaleengineer.com/dsa/problems/maximum-difference-between-even-and-odd-frequency-i
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
---
## Problem
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.

# Approaches
## Brute-Force on Frequencies
This approach first calculates the frequency of each character. Then, it separates the characters into two groups: those with odd frequencies and those with even frequencies. Finally, it iterates through all possible pairs of one character from the odd-frequency group and one from the even-frequency group to find the maximum possible difference.
**Time:** O(N + K^2), where N is the length of the string and K is the number of unique characters (at most 26).
- O(N) to iterate through the string and build the frequency map.
- O(K) to populate the odd and even frequency lists.
- O(K_odd * K_even) for the nested loops, which is O(K^2) in the worst case.
Since K is a constant (26), the overall complexity is dominated by the initial string traversal, making it effectively O(N). However, it's conceptually less efficient due to the nested loops. · **Space:** O(K), where K is the number of unique characters (at most 26). This space is used for the frequency map and the two lists to store odd and even frequencies. Since K is constant, this is considered O(1) space.
**Pros:** Simple to understand and implement.; Correctly solves the problem.
**Cons:** Less efficient than the optimal approach due to the nested loops that check all pairs of odd and even frequencies, which is unnecessary.
### Explanation
To solve the problem, we can start by counting how many times each character appears in the string. A hash map is a suitable data structure for this. After counting, we can segregate the frequencies into two separate lists: one for odd frequencies and one for even frequencies. To find the maximum difference, we need to find an odd frequency `a1` and an even frequency `a2` such that `a1 - a2` is maximized. This is equivalent to finding the largest value in the `oddFrequencies` list and the smallest value in the `evenFrequencies` list. This brute-force method checks every possible pair of an odd frequency and an even frequency to find this maximum difference.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int maxDifference(String s) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        List<Integer> oddFrequencies = new ArrayList<>();
        List<Integer> evenFrequencies = new ArrayList<>();

        for (int freq : freqMap.values()) {
            if (freq % 2 != 0) {
                oddFrequencies.add(freq);
            } else {
                evenFrequencies.add(freq);
            }
        }

        int maxDifference = Integer.MIN_VALUE;
        for (int oddFreq : oddFrequencies) {
            for (int evenFreq : evenFrequencies) {
                maxDifference = Math.max(maxDifference, oddFreq - evenFreq);
            }
        }

        return maxDifference;
    }
}
```
### Algorithm
- Create a frequency map (e.g., a `HashMap` or an array of size 26) to store the counts of each character in the string `s`.
- Iterate through the string `s` to populate the frequency map.
- Create two lists: `oddFrequencies` and `evenFrequencies`.
- Iterate through the values in the frequency map. If a frequency is non-zero, add it to the `oddFrequencies` list if it's odd, or to the `evenFrequencies` list if it's even.
- Initialize a variable `maxDifference` to a very small number (e.g., `Integer.MIN_VALUE`).
- Use nested loops to iterate through every frequency `oddFreq` in `oddFrequencies` and every frequency `evenFreq` in `evenFrequencies`.
- For each pair, calculate the difference `oddFreq - evenFreq` and update `maxDifference` if this difference is larger.
- Return `maxDifference`.

## Optimal Single Pass over Frequencies
This is the most efficient approach. It recognizes that to maximize the difference `freq(a1) - freq(a2)`, we only need the *maximum* odd frequency and the *minimum* even frequency. The approach first calculates all character frequencies in a single pass. Then, in a second pass over the frequencies, it finds the maximum odd frequency and the minimum even frequency simultaneously.
**Time:** O(N), where N is the length of the string.
- O(N) to iterate through the string and populate the frequency array.
- O(K) to iterate through the frequency array, where K is the alphabet size (26).
The total time complexity is O(N + K). Since K is a constant, this simplifies to O(N). · **Space:** O(1). We use a fixed-size array of 26 integers to store frequencies, which does not depend on the input string size. Therefore, the space complexity is constant.
**Pros:** Highly efficient in both time and space.; Solves the problem in a single pass over the frequencies after the initial count.; Avoids unnecessary comparisons by directly targeting the maximum odd and minimum even frequencies.
**Cons:** No significant cons; this is the optimal solution for the given constraints.
### Explanation
To maximize the expression `freq(a1) - freq(a2)`, where `freq(a1)` is odd and `freq(a2)` is even, we should choose the largest possible odd frequency and the smallest possible even frequency. This insight allows us to avoid comparing all pairs.

The algorithm proceeds as follows:
1. First, we count the frequency of each character. Since the input consists only of lowercase English letters, a simple array of size 26 is sufficient and efficient for this task.
2. We then iterate through this frequency array. We maintain two variables: `maxOddFreq` to track the largest odd frequency seen so far, and `minEvenFreq` to track the smallest even frequency seen so far.
3. During the iteration, if we encounter an odd frequency, we compare it with `maxOddFreq` and update if it's larger. If we encounter an even frequency, we compare it with `minEvenFreq` and update if it's smaller.
4. After checking all character frequencies, the final answer is simply `maxOddFreq - minEvenFreq`.

```java
class Solution {
    public int maxDifference(String s) {
        int[] frequencies = new int[26];
        for (char c : s.toCharArray()) {
            frequencies[c - 'a']++;
        }

        int maxOddFreq = Integer.MIN_VALUE;
        int minEvenFreq = Integer.MAX_VALUE;

        for (int freq : frequencies) {
            if (freq == 0) {
                continue; // Skip characters not present in the string
            }
            if (freq % 2 != 0) { // Odd frequency
                maxOddFreq = Math.max(maxOddFreq, freq);
            } else { // Even frequency
                minEvenFreq = Math.min(minEvenFreq, freq);
            }
        }

        // The problem guarantees both types of frequencies exist.
        return maxOddFreq - minEvenFreq;
    }
}
```
### Algorithm
- Initialize an integer array `frequencies` of size 26 to all zeros. This array will map each lowercase letter to its frequency.
- Iterate through the input string `s`. For each character `c`, increment the count at `frequencies[c - 'a']`.
- Initialize two variables: `maxOddFreq` to a very small number (e.g., `Integer.MIN_VALUE`) and `minEvenFreq` to a very large number (e.g., `Integer.MAX_VALUE`).
- Iterate through the `frequencies` array from index 0 to 25.
- For each frequency `freq` in the array that is greater than 0:
  - If `freq` is odd, update `maxOddFreq = Math.max(maxOddFreq, freq)`.
  - If `freq` is even, update `minEvenFreq = Math.min(minEvenFreq, freq)`.
- The problem guarantees that at least one character with an odd frequency and one with an even frequency exist, so `maxOddFreq` and `minEvenFreq` will be updated correctly.
- Return the final result: `maxOddFreq - minEvenFreq`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MaxDifference(string s) {
        int[] cnt = new int[26];
        foreach(char c in s) {
            ++cnt[c - 'a'];
        }
        int a = 0, b = 1 << 30;
        foreach(int v in cnt) {
            if (v % 2 == 1) {
                a = Math.Max(a, v);
            } else if (v > 0) {
                b = Math.Min(b, v);
            }
        }
        return a - b;
    }
}
```

### Java

```java
class Solution {
public
  int maxDifference(String s) {
    int[] cnt = new int[26];
    for (char c : s.toCharArray()) {
      ++cnt[c - 'a'];
    }
    int a = 0, b = 1 << 30;
    for (int v : cnt) {
      if (v % 2 == 1) {
        a = Math.max(a, v);
      } else if (v > 0) {
        b = Math.min(b, v);
      }
    }
    return a - b;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxDifference(string s) {
    int cnt[26]{};
    for (char c : s) {
      ++cnt[c - 'a'];
    }
    int a = 0, b = 1 << 30;
    for (int v : cnt) {
      if (v % 2 == 1) {
        a = max(a, v);
      } else if (v > 0) {
        b = min(b, v);
      }
    }
    return a - b;
  }
};

```

### Python

```python
class Solution:
    def maxDifference(self, s: str) -> int: cnt = Counter(s) a, b = 0, inf for v in cnt . values(): if v % 2: a = max(a, v) else: b = min(b, v) return a - b

```