3442: Maximum Difference Between Even and Odd Frequency I
Problem Statement
Given a string s consisting of lowercase English letters, 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:
- 'a' has odd frequency of 5
- 'b' has even frequency of 2
- Maximum difference: 5 - 2 = 3Example 2
Input: s = "abcabcab"
Output: 1
Explanation:
- 'a' has odd frequency of 3
- 'c' has even frequency of 2
- Maximum difference: 3 - 2 = 1Approach 1: Frequency Counting with Lists
This approach counts character frequencies, separates odd and even frequencies into lists, then calculates max odd frequency minus min even frequency.
Algorithm Steps
- Count frequency of each character using a frequency map
- Separate frequencies into odd and even lists
- Find maximum value in odd frequencies list
- Find minimum value in even frequencies list
- Return max_odd - min_even
class Solution {
public:
int maximumDifference(string s) {
unordered_map<char, int> freq;
for (char c : s) {
freq[c]++;
}
vector<int> oddFreq, evenFreq;
for (auto& [ch, count] : freq) {
if (count % 2 == 1) {
oddFreq.push_back(count);
} else {
evenFreq.push_back(count);
}
}
int maxOdd = *max_element(oddFreq.begin(), oddFreq.end());
int minEven = *min_element(evenFreq.begin(), evenFreq.end());
return maxOdd - minEven;
}
};class Solution {
public int maximumDifference(String s) {
int[] freq = new int[26];
for (char c : s.toCharArray()) {
freq[c - 'a']++;
}
List<Integer> oddFreq = new ArrayList<>();
List<Integer> evenFreq = new ArrayList<>();
for (int count : freq) {
if (count == 0) continue;
if (count % 2 == 1) {
oddFreq.add(count);
} else {
evenFreq.add(count);
}
}
int maxOdd = Collections.max(oddFreq);
int minEven = Collections.min(evenFreq);
return maxOdd - minEven;
}
}class Solution:
def maximumDifference(self, s: str) -> int:
freq = {}
for c in s:
freq[c] = freq.get(c, 0) + 1
odd_freq = []
even_freq = []
for count in freq.values():
if count % 2 == 1:
odd_freq.append(count)
else:
even_freq.append(count)
return max(odd_freq) - min(even_freq)Approach 2: Optimized Single Pass
This approach tracks max odd and min even frequencies in a single pass through frequency counts.
class Solution {
public:
int maximumDifference(string s) {
int freq[26] = {0};
for (char c : s) {
freq[c - 'a']++;
}
int maxOdd = INT_MIN;
int minEven = INT_MAX;
for (int count : freq) {
if (count == 0) continue;
if (count % 2 == 1) {
if (count > maxOdd) maxOdd = count;
} else {
if (count < minEven) minEven = count;
}
}
return maxOdd - minEven;
}
};class Solution {
public int maximumDifference(String s) {
int[] freq = new int[26];
for (char c : s.toCharArray()) {
freq[c - 'a']++;
}
int maxOdd = Integer.MIN_VALUE;
int minEven = Integer.MAX_VALUE;
for (int count : freq) {
if (count == 0) continue;
if (count % 2 == 1) {
if (count > maxOdd) maxOdd = count;
} else {
if (count < minEven) minEven = count;
}
}
return maxOdd - minEven;
}
}class Solution:
def maximumDifference(self, s: str) -> int:
freq = [0] * 26
for c in s:
freq[ord(c) - ord('a')] += 1
max_odd = -10**9
min_even = 10**9
for count in freq:
if count == 0:
continue
if count % 2 == 1:
if count > max_odd:
max_odd = count
else:
if count < min_even:
min_even = count
return max_odd - min_evenApproach 3: Functional Programming (Python)
Concise implementation using Python's collection processing features.
from collections import Counter
class Solution:
def maximumDifference(self, s: str) -> int:
freq = Counter(s)
odd = [count for count in freq.values() if count % 2 == 1]
even = [count for count in freq.values() if count % 2 == 0]
return max(odd) - min(even)Approach Comparison
| Approach | Time | Space | Best For |
|---|---|---|---|
| Frequency Lists | O(n) | O(1) | Readability |
| Optimized Single Pass | O(n) | O(1) | Efficiency |
| Functional | O(n) | O(1) | Conciseness |
Edge Cases
1. Minimum String Length (n=3)
Input: "abc" → Output: 1-0?
But: a:1(odd), b:1(odd), c:1(odd) → no even!
Constraint: "at least one character with an odd frequency and one with an even frequency"2. All Characters Same
Input: "aaaa" → Output: 0?
Freq: a:4(even) → but no odd! → constraint guarantees both exist3. Mixed Frequencies
Input: "aabbc" →
a:2(even), b:2(even), c:1(odd) → maxOdd=1, minEven=2 → 1-2=-1Frequently Asked Questions
Why calculate max odd - min even specifically?
This combination maximizes the difference because we want the largest possible positive value from (odd_freq - even_freq).
Can the difference be negative?
Yes, if all odd frequencies are smaller than all even frequencies, the result will be negative. The problem asks for maximum difference, which could be negative.
How to handle uppercase letters?
The problem specifies lowercase English letters, so no handling needed. For case-insensitive versions, convert to lowercase first.
What if there are multiple characters with same frequency?
The algorithm considers frequency values, not characters, so duplicates don't affect the result.
Why use INT_MIN and INT_MAX in optimized approach?
This initializes variables to safely compare against the first valid frequency value encountered.
Can we solve without a frequency map?
No, since we need exact frequency counts for each character to determine odd/even status.
How does this handle non-alphabet characters?
The problem states only lowercase English letters, so no special handling needed.
Is 0 considered an even frequency?
Yes, but characters with 0 frequency are not present in the string and are excluded from consideration.
What's the space complexity for these solutions?
O(1) - constant space since we only store frequencies for 26 possible characters.
Can we optimize further?
We can combine frequency counting with tracking maxOdd/minEven in a single pass, but big-O complexity remains the same.