Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Build confidence with an intuition-first walkthrough focused on hash map fundamentals.
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:
'a' has an odd frequency of 5, and 'b' has an even frequency of 2.5 - 2 = 3.Example 2:
Input: s = "abcabcab"
Output: 1
Explanation:
'a' has an odd frequency of 3, and 'c' has an even frequency of 2.3 - 2 = 1.Constraints:
3 <= s.length <= 100s consists only of lowercase English letters.s contains at least one character with an odd frequency and one with an even frequency.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map
"aaaaabbc"
"abcabcab"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3442: Maximum Difference Between Even and Odd Frequency I
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;
}
}
// Accepted solution for LeetCode #3442: Maximum Difference Between Even and Odd Frequency I
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
}
# Accepted solution for LeetCode #3442: Maximum Difference Between Even and Odd Frequency I
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
// Accepted solution for LeetCode #3442: Maximum Difference Between Even and Odd Frequency I
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
}
}
// Accepted solution for LeetCode #3442: Maximum Difference Between Even and Odd Frequency I
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;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.