Prerequisites
Before attempting this problem, you should be comfortable with:
- Hash Maps / Frequency Counting - Counting occurrences of elements using dictionaries or arrays
- Parity (Odd/Even) - Determining whether a number is odd or even using modulo or bitwise operations
1. Counting
Intuition
We want to maximize (frequency of some character with odd count) - (frequency of some character with even count). The straightforward approach is to count how often each character appears, then check all pairs where one has an odd frequency and the other has an even frequency. We take the maximum difference among all valid pairs.
Algorithm
- Count the frequency of each character in the string.
- Iterate through all pairs of frequencies where one is odd and one is even.
- For each valid pair, compute
odd - even and track the maximum.
- Return the maximum difference found.
class Solution:
def maxDifference(self, s: str) -> int:
count = Counter(s)
res = float("-inf")
for odd in count.values():
if odd % 2 == 0: continue
for even in count.values():
if even % 2 == 1: continue
res = max(res, odd - even)
return res
public class Solution {
public int maxDifference(String s) {
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
int res = Integer.MIN_VALUE;
for (int odd : count) {
if (odd == 0 || odd % 2 == 0) continue;
for (int even : count) {
if (even == 0 || even % 2 == 1) continue;
res = Math.max(res, odd - even);
}
}
return res;
}
}
class Solution {
public:
int maxDifference(string s) {
vector<int> count(26, 0);
for (char c : s) {
count[c - 'a']++;
}
int res = INT_MIN;
for (int odd : count) {
if (odd == 0 || odd % 2 == 0) continue;
for (int even : count) {
if (even == 0 || even % 2 == 1) continue;
res = max(res, odd - even);
}
}
return res;
}
};
class Solution {
maxDifference(s) {
const count = new Array(26).fill(0);
for (const c of s) {
count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
let res = -Infinity;
for (const odd of count) {
if (odd === 0 || odd % 2 === 0) continue;
for (const even of count) {
if (even === 0 || even % 2 === 1) continue;
res = Math.max(res, odd - even);
}
}
return res;
}
}
public class Solution {
public int MaxDifference(string s) {
int[] count = new int[26];
foreach (char c in s) {
count[c - 'a']++;
}
int res = int.MinValue;
foreach (int odd in count) {
if (odd == 0 || odd % 2 == 0) continue;
foreach (int even in count) {
if (even == 0 || even % 2 == 1) continue;
res = Math.Max(res, odd - even);
}
}
return res;
}
}
func maxDifference(s string) int {
count := make([]int, 26)
for _, c := range s {
count[c-'a']++
}
res := -1 << 31
for _, odd := range count {
if odd == 0 || odd%2 == 0 {
continue
}
for _, even := range count {
if even == 0 || even%2 == 1 {
continue
}
if odd-even > res {
res = odd - even
}
}
}
return res
}
class Solution {
fun maxDifference(s: String): Int {
val count = IntArray(26)
for (c in s) {
count[c - 'a']++
}
var res = Int.MIN_VALUE
for (odd in count) {
if (odd == 0 || odd % 2 == 0) continue
for (even in count) {
if (even == 0 || even % 2 == 1) continue
res = maxOf(res, odd - even)
}
}
return res
}
}
class Solution {
func maxDifference(_ s: String) -> Int {
var count = [Int](repeating: 0, count: 26)
let aAscii = Character("a").asciiValue!
for c in s {
count[Int(c.asciiValue! - aAscii)] += 1
}
var res = Int.min
for odd in count {
if odd == 0 || odd % 2 == 0 { continue }
for even in count {
if even == 0 || even % 2 == 1 { continue }
res = max(res, odd - even)
}
}
return res
}
}
impl Solution {
pub fn max_difference(s: String) -> i32 {
let mut count = [0i32; 26];
for c in s.bytes() {
count[(c - b'a') as usize] += 1;
}
let mut res = i32::MIN;
for &odd in &count {
if odd == 0 || odd % 2 == 0 { continue; }
for &even in &count {
if even == 0 || even % 2 == 1 { continue; }
res = res.max(odd - even);
}
}
res
}
}
Time & Space Complexity
- Time complexity: O(n)
- Space complexity: O(1) since we have at most 26 different characters.
2. Counting (Optimal)
Intuition
Instead of checking all pairs, we can observe that to maximize odd - even, we should pick the largest odd frequency and the smallest even frequency. This gives us the optimal answer in a single pass through the frequency counts.
Algorithm
- Count the frequency of each character in the string.
- Track
oddMax as the largest frequency that is odd.
- Track
evenMin as the smallest frequency that is even (and greater than 0).
- Return
oddMax - evenMin.
class Solution:
def maxDifference(self, s: str) -> int:
count = Counter(s)
oddMax, evenMin = 0, len(s)
for cnt in count.values():
if cnt & 1:
oddMax = max(oddMax, cnt)
else:
evenMin = min(evenMin, cnt)
return oddMax - evenMin
public class Solution {
public int maxDifference(String s) {
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
int oddMax = 0, evenMin = s.length();
for (int c : count) {
if ((c & 1) == 1) {
oddMax = Math.max(oddMax, c);
} else if (c > 0) {
evenMin = Math.min(evenMin, c);
}
}
return oddMax - evenMin;
}
}
class Solution {
public:
int maxDifference(string s) {
vector<int> count(26, 0);
for (char c : s) {
count[c - 'a']++;
}
int oddMax = 0, evenMin = s.length();
for (int c : count) {
if (c & 1) {
oddMax = max(oddMax, c);
} else if (c > 0) {
evenMin = min(evenMin, c);
}
}
return oddMax - evenMin;
}
};
class Solution {
maxDifference(s) {
const count = new Array(26).fill(0);
for (const c of s) {
count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
let oddMax = 0,
evenMin = s.length;
for (const c of count) {
if (c & 1) {
oddMax = Math.max(oddMax, c);
} else if (c > 0) {
evenMin = Math.min(evenMin, c);
}
}
return oddMax - evenMin;
}
}
public class Solution {
public int MaxDifference(string s) {
int[] count = new int[26];
foreach (char c in s) {
count[c - 'a']++;
}
int oddMax = 0, evenMin = s.Length;
foreach (int c in count) {
if ((c & 1) == 1) {
oddMax = Math.Max(oddMax, c);
} else if (c > 0) {
evenMin = Math.Min(evenMin, c);
}
}
return oddMax - evenMin;
}
}
func maxDifference(s string) int {
count := make([]int, 26)
for _, c := range s {
count[c-'a']++
}
oddMax, evenMin := 0, len(s)
for _, c := range count {
if c&1 == 1 {
if c > oddMax {
oddMax = c
}
} else if c > 0 {
if c < evenMin {
evenMin = c
}
}
}
return oddMax - evenMin
}
class Solution {
fun maxDifference(s: String): Int {
val count = IntArray(26)
for (c in s) {
count[c - 'a']++
}
var oddMax = 0
var evenMin = s.length
for (c in count) {
if (c and 1 == 1) {
oddMax = maxOf(oddMax, c)
} else if (c > 0) {
evenMin = minOf(evenMin, c)
}
}
return oddMax - evenMin
}
}
class Solution {
func maxDifference(_ s: String) -> Int {
var count = [Int](repeating: 0, count: 26)
let aAscii = Character("a").asciiValue!
for c in s {
count[Int(c.asciiValue! - aAscii)] += 1
}
var oddMax = 0
var evenMin = s.count
for c in count {
if c & 1 == 1 {
oddMax = max(oddMax, c)
} else if c > 0 {
evenMin = min(evenMin, c)
}
}
return oddMax - evenMin
}
}
impl Solution {
pub fn max_difference(s: String) -> i32 {
let mut count = [0i32; 26];
for c in s.bytes() {
count[(c - b'a') as usize] += 1;
}
let mut odd_max = 0;
let mut even_min = s.len() as i32;
for &c in &count {
if c & 1 == 1 {
odd_max = odd_max.max(c);
} else if c > 0 {
even_min = even_min.min(c);
}
}
odd_max - even_min
}
}
Time & Space Complexity
- Time complexity: O(n)
- Space complexity: O(1) since we have at most 26 different characters.
Common Pitfalls
Including Zero Frequencies
Characters that do not appear in the string have frequency zero, which is technically even. However, you cannot use a zero-frequency character as the "even frequency" character because it does not exist in the string. Always filter out zero counts when looking for the minimum even frequency.
Swapping Odd and Even in the Difference
The problem asks for (odd frequency) - (even frequency), not the other way around. Maximizing even - odd instead gives the wrong answer. Pay attention to which frequency should be maximized and which should be minimized.
