Maximum Difference Between Even and Odd Frequency I solution and explanation
Google
9 more videos on this problem
Maximum Difference Between Even and Odd Frequency I | Easy | Leetcode 3442 | codestorywithMIKcodestorywithMIK · 6:30 · 4K views
3442. Maximum Difference Between Even and Odd Frequency I | Leetcode Daily - PythonLeetcode Daily · 5:39 · 567 views
Daily Leetcode #1897: Jun 10, 2025 - 3442. Maximum Difference Between Even and Odd Frequency IProgramming Live with Larry · 4:20 · 437 views
Maximum Difference Between Even and Odd Frequency I | LeetCode 3442 | Java Code | Developer CoderDeveloper Coder · 9:11 · 332 views
Leetcode | 3442 Maximum Difference Between Even ans Odd Frequency I | Java | Hashing | WeeklyCakot Coding · 9:37 · 329 views
3442. Maximum Difference Between Even and Odd Frequency I | Java SolutioncodingX krishna · 6:56 · 231 views
3442. Maximum Difference Between Even and Odd Frequency I - LeetCode [Easy] - 10 June 2025Intuit & Code · 14:16 · 225 views
3442. Maximum Difference Between Even and Odd Frequency I (Leetcode Easy)Programming Live with Larry · 4:58 · 211 views
3442: Maximum Difference Between Even and Odd Frequency I | Python Solution | LeetCode🔥BugNoJutsu · 2:05 · 169 views
Maximum Difference Between Even and Odd Frequency I | LeetCode 3442 - Pythonimpoldev · 5:10 · 165 views
The 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:
a1has an odd frequency in the string.a2has 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 of5, and'b'has an even frequency of2. - The maximum difference is
5 - 2 = 3.
Example 2:
Input: s = "abcabcab"
Output: 1
Explanation:
- The character
'a'has an odd frequency of3, and'c'has an even frequency of 2. - The maximum difference is
3 - 2 = 1.
Constraints:
3 <= s.length <= 100sconsists only of lowercase English letters.scontains at least one character with an odd frequency and one with an even frequency.
Approach overview
Problem Overview: You are given a string and need to compare character frequencies. The goal is to choose one character with an odd frequency and another with an even frequency, then maximize the difference oddFreq - evenFreq. If no valid pair exists, the result is typically -1.
Approach 1: Brute Force Frequency Comparison (O(n + k^2) time, O(k) space)
Start by computing the frequency of each character in the string using a map or array. After collecting all counts, separate them into two groups: characters with odd frequencies and characters with even frequencies. Compare every odd frequency with every even frequency and track the maximum difference. The complexity comes from pairwise comparisons across the two groups. This works because the number of unique characters k is small, but it is still unnecessary work when the optimal values can be derived directly.
Approach 2: Counting + Greedy Extremes (O(n + k) time, O(k) space)
The optimal approach relies on a simple observation: the maximum value of oddFreq - evenFreq will always come from the largest odd frequency and the smallest even frequency. First count character frequencies using a hash map or fixed-size array (typical for lowercase strings). Then iterate through the counts once to track two values: maxOdd and minEven. If both exist, compute maxOdd - minEven. If either group is missing, no valid pair can be formed.
This method reduces the problem to a single counting pass followed by a scan over the frequency values. The algorithm uses constant extra work per character and avoids any nested comparisons. Counting problems like this commonly appear in string interviews and are best handled with structures from hash tables or simple arrays.
The approach also highlights a common interview pattern: reduce a comparison problem into tracking extreme values during iteration. Instead of storing and comparing every candidate pair, maintain the best odd and even candidates while scanning.
Recommended for interviews: The counting approach is the expected solution. Interviewers want to see you quickly build a frequency map (a standard string technique) and reason about extremes rather than brute-force comparisons. Mentioning the brute-force idea first shows understanding, but implementing the counting optimization demonstrates stronger problem-solving skills.
Solution
We can use a hash table or an array cnt to record the occurrences of each character in the string s. Then, we traverse cnt to find the maximum frequency a of characters that appear an odd number of times and the minimum frequency b of characters that appear an even number of times. Finally, we return a - b.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(|\Sigma|), where \Sigma is the character set. In this problem, |\Sigma| = 26.
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 - bclass 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;
}
}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;
}
};function maxDifference(s: string): number {
const cnt: Record<string, number> = {};
for (const c of s) {
cnt[c] = (cnt[c] || 0) + 1;
}
let [a, b] = [0, Infinity];
for (const [_, v] of Object.entries(cnt)) {
if (v % 2 === 1) {
a = Math.max(a, v);
} else {
b = Math.min(b, v);
}
}
return a - b;
}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;
}
}func maxDifference(s string) int {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
a, b := 0, 1<<30
for _, v := range cnt {
if v%2 == 1 {
a = max(a, v)
} else if v > 0 {
b = min(b, v)
}
}
return a - b
}impl Solution {
pub fn max_difference(s: String) -> i32 {
let mut cnt = [0; 26];
for c in s.bytes() {
cnt[(c - b'a') as usize] += 1;
}
let mut a = 0;
let mut b = 1 << 30;
for &v in cnt.iter() {
if v % 2 == 1 {
a = a.max(v);
} else if v > 0 {
b = b.min(v);
}
}
a - b
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Frequency Comparison | O(n + k^2) | O(k) | Useful for understanding the problem before optimizing |
| Counting with Extreme Tracking | O(n + k) | O(k) | Best general solution for strings using frequency counting |
Frequently asked questions
Is Maximum Difference Between Even and Odd Frequency I easy or hard?
Maximum Difference Between Even and Odd Frequency I is categorized as an Easy problem. The main concept is basic frequency counting on strings and checking whether counts are odd or even, which is a common beginner-friendly interview pattern.
Maximum Difference Between Even and Odd Frequency I Python/Java solution
Most implementations use a dictionary or array to count characters, then scan the counts to find the largest odd and smallest even values. The logic is identical across Python, Java, C++, Go, and TypeScript, differing only in syntax for maps and loops.
How to solve Maximum Difference Between Even and Odd Frequency I in O(n)?
First count the frequency of each character in the string using an array or hash map. Then iterate through those counts and track two values: the largest odd frequency and the smallest even frequency. Compute their difference if both exist. Each step scans the data once, giving O(n) overall complexity.
What is the best approach for Maximum Difference Between Even and Odd Frequency I?
The best approach is frequency counting with extreme tracking. Count occurrences of each character, then find the maximum odd frequency and the minimum even frequency. The final answer is maxOdd - minEven. This runs in O(n) time with O(k) space, where k is the number of unique characters.
Is Maximum Difference Between Even and Odd Frequency I asked at Google/Amazon/Meta?
Frequency counting and parity-based string problems are common in interviews at companies like Amazon, Google, and Meta. While this exact question may not appear frequently, the underlying pattern—counting characters and comparing frequency properties—is a standard interview topic.
What data structure is used in Maximum Difference Between Even and Odd Frequency I?
The main data structure is a hash table or fixed-size frequency array. It stores the count of each character in the string. After counting, simple variables track the maximum odd and minimum even frequencies.
What is the time complexity of Maximum Difference Between Even and Odd Frequency I?
The optimal solution runs in O(n + k) time. n is the length of the string used to build the frequency map, and k is the number of unique characters scanned to find the maximum odd and minimum even frequencies. Space complexity is O(k).