LeetCode 3442: Maximum Difference Between Even and Odd Frequency I (Parity Frequency Extremes)
LeetCode 3442StringCountingFrequencyToday we solve LeetCode 3442 - Maximum Difference Between Even and Odd Frequency I.
Source: https://leetcode.com/problems/maximum-difference-between-even-and-odd-frequency-i/
English
Problem Summary
Given a lowercase string s, choose one character with odd frequency and one with even frequency. Return the maximum possible value of oddFreq - evenFreq.
Key Insight
To maximize oddFreq - evenFreq, we only need:
- the largest odd frequency, and
- the smallest even frequency (greater than 0).
Algorithm
1) Count frequency of all 26 letters.
2) Scan counts once:
- if count is odd, update maxOdd
- if count is even and positive, update minEven
3) Return maxOdd - minEven.
Complexity Analysis
Time: O(n + 26) = O(n).
Space: O(26) = O(1).
Common Pitfalls
- Treating zero as a valid even frequency.
- Looking for all pairs instead of tracking two extremes.
- Forgetting to initialize maxOdd / minEven with safe sentinels.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int maxDifference(String s) {
int[] cnt = new int[26];
for (int i = 0; i < s.length(); i++) {
cnt[s.charAt(i) - 'a']++;
}
int maxOdd = Integer.MIN_VALUE;
int minEven = Integer.MAX_VALUE;
for (int c : cnt) {
if (c == 0) continue;
if ((c & 1) == 1) {
maxOdd = Math.max(maxOdd, c);
} else {
minEven = Math.min(minEven, c);
}
}
return maxOdd - minEven;
}
}func maxDifference(s string) int {
cnt := make([]int, 26)
for _, ch := range s {
cnt[ch-'a']++
}
maxOdd := -1 << 30
minEven := 1 << 30
for _, c := range cnt {
if c == 0 {
continue
}
if c%2 == 1 {
if c > maxOdd {
maxOdd = c
}
} else {
if c < minEven {
minEven = c
}
}
}
return maxOdd - minEven
}class Solution {
public:
int maxDifference(string s) {
vector<int> cnt(26, 0);
for (char ch : s) cnt[ch - 'a']++;
int maxOdd = INT_MIN;
int minEven = INT_MAX;
for (int c : cnt) {
if (c == 0) continue;
if (c % 2 == 1) {
maxOdd = max(maxOdd, c);
} else {
minEven = min(minEven, c);
}
}
return maxOdd - minEven;
}
};class Solution:
def maxDifference(self, s: str) -> int:
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - ord('a')] += 1
max_odd = -10**9
min_even = 10**9
for c in cnt:
if c == 0:
continue
if c % 2 == 1:
max_odd = max(max_odd, c)
else:
min_even = min(min_even, c)
return max_odd - min_evenvar maxDifference = function(s) {
const cnt = new Array(26).fill(0);
for (const ch of s) {
cnt[ch.charCodeAt(0) - 97]++;
}
let maxOdd = -Infinity;
let minEven = Infinity;
for (const c of cnt) {
if (c === 0) continue;
if ((c & 1) === 1) {
maxOdd = Math.max(maxOdd, c);
} else {
minEven = Math.min(minEven, c);
}
}
return maxOdd - minEven;
};中文
题目概述
给定一个仅含小写字母的字符串 s，选一个出现次数为奇数的字符和一个出现次数为偶数的字符，最大化 oddFreq - evenFreq。
核心思路
要让差值最大，本质上只需要两件事：
- 找到最大的奇数频次 maxOdd
- 找到最小的偶数频次 minEven（且频次必须大于 0）
答案就是 maxOdd - minEven。
算法步骤
1）统计 26 个字母的出现次数。
2）遍历计数数组：
- 若为奇数，更新 maxOdd
- 若为偶数且非 0，更新 minEven
3）返回 maxOdd - minEven。
复杂度分析
时间复杂度：O(n + 26)，即 O(n)。
空间复杂度：O(26)，即 O(1)。
常见陷阱
- 把 0 当作有效偶数频次参与计算。
- 误以为要枚举所有字符对，导致不必要的复杂度。
- 初始化边界值不当，造成极值更新错误。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int maxDifference(String s) {
int[] cnt = new int[26];
for (int i = 0; i < s.length(); i++) {
cnt[s.charAt(i) - 'a']++;
}
int maxOdd = Integer.MIN_VALUE;
int minEven = Integer.MAX_VALUE;
for (int c : cnt) {
if (c == 0) continue;
if ((c & 1) == 1) {
maxOdd = Math.max(maxOdd, c);
} else {
minEven = Math.min(minEven, c);
}
}
return maxOdd - minEven;
}
}func maxDifference(s string) int {
cnt := make([]int, 26)
for _, ch := range s {
cnt[ch-'a']++
}
maxOdd := -1 << 30
minEven := 1 << 30
for _, c := range cnt {
if c == 0 {
continue
}
if c%2 == 1 {
if c > maxOdd {
maxOdd = c
}
} else {
if c < minEven {
minEven = c
}
}
}
return maxOdd - minEven
}class Solution {
public:
int maxDifference(string s) {
vector<int> cnt(26, 0);
for (char ch : s) cnt[ch - 'a']++;
int maxOdd = INT_MIN;
int minEven = INT_MAX;
for (int c : cnt) {
if (c == 0) continue;
if (c % 2 == 1) {
maxOdd = max(maxOdd, c);
} else {
minEven = min(minEven, c);
}
}
return maxOdd - minEven;
}
};class Solution:
def maxDifference(self, s: str) -> int:
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - ord('a')] += 1
max_odd = -10**9
min_even = 10**9
for c in cnt:
if c == 0:
continue
if c % 2 == 1:
max_odd = max(max_odd, c)
else:
min_even = min(min_even, c)
return max_odd - min_evenvar maxDifference = function(s) {
const cnt = new Array(26).fill(0);
for (const ch of s) {
cnt[ch.charCodeAt(0) - 97]++;
}
let maxOdd = -Infinity;
let minEven = Infinity;
for (const c of cnt) {
if (c === 0) continue;
if ((c & 1) === 1) {
maxOdd = Math.max(maxOdd, c);
} else {
minEven = Math.min(minEven, c);
}
}
return maxOdd - minEven;
};
Comments