Problem statement

You are given a string s of lowercase English letters.

Choose two characters a1 and a2 of s such that a1 occurs an odd number of times in s and a2 occurs an even number of times. Return the largest possible value of freq(a1) - freq(a2).

s is guaranteed to contain at least one character with an odd frequency and at least one with an even frequency.

Example 1

Input: s = "cccccdde"
Output: 3
Explanation: `c` occurs 5 times (odd) and `d` twice (even): `5 - 2 = 3`.

Example 2

Input: s = "abbbbcc"
Output: -1
Explanation: Odd: `a` (1). Even: `b` (4), `c` (2). The best is `1 - 2 = -1`.

Example 3

Input: s = "zzzyyyyyyx"
Output: -3
Explanation: Odd: `z` (3), `x` (1). Even: `y` (6). The best is `3 - 6 = -3`.

Constraints

• 3 <= s.length <= 100
• s consists only of lowercase English letters
• s contains at least one character with an odd frequency and one with an even frequency

Hints for Maximum Difference Between Even and Odd Frequency I

1. Hint 1

   Count each letter's frequency first.

2. Hint 2

   To make the difference as large as possible, take the largest odd frequency and subtract the smallest (non-zero) even frequency.

How to solve Maximum Difference Between Even and Odd Frequency I

The two choices are independent: the difference is maximised by the largest odd frequency minus the smallest even frequency among the letters that actually occur.

Approach

1. Count the 26 letter frequencies.
2. Over the letters with an odd count, take the maximum maxOdd.
3. Over the letters with a non-zero even count, take the minimum minEven.
4. Return maxOdd - minEven.

Why it works

freq(a1) - freq(a2) grows with freq(a1) and shrinks with freq(a2), and the two characters are chosen from disjoint groups (odd versus even counts), so each can be optimised on its own.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Letters that do not occur have frequency 0, which is even — they must be excluded, or minEven collapses to 0.
• The answer can be negative.

Reference solution

Python

def maxDifference(s: str) -> int:
    freq = [0] * 26
    for ch in s:
        freq[ord(ch) - 97] += 1
    max_odd = max(f for f in freq if f % 2 == 1)
    min_even = min(f for f in freq if f > 0 and f % 2 == 0)
    return max_odd - min_even

Java

public static int maxDifference(String s) {
    int[] freq = new int[26];
    for (int i = 0; i < s.length(); i++) freq[s.charAt(i) - 'a']++;
    int maxOdd = 0, minEven = 1000;
    for (int f : freq) {
        if (f % 2 == 1) maxOdd = Math.max(maxOdd, f);
        else if (f > 0) minEven = Math.min(minEven, f);
    }
    return maxOdd - minEven;
}

C++

int maxDifference(string s) {
    int freq[26] = {0};
    for (char c : s) freq[c - 'a']++;
    int maxOdd = 0, minEven = 1000;
    for (int f : freq) {
        if (f % 2 == 1) maxOdd = max(maxOdd, f);
        else if (f > 0) minEven = min(minEven, f);
    }
    return maxOdd - minEven;
}

JavaScript

var maxDifference = function(s) {
    var freq = new Array(26).fill(0);
    for (var i = 0; i < s.length; i++) freq[s.charCodeAt(i) - 97]++;
    var maxOdd = 0, minEven = 1000;
    for (var c = 0; c < 26; c++) {
        var f = freq[c];
        if (f % 2 === 1) maxOdd = Math.max(maxOdd, f);
        else if (f > 0) minEven = Math.min(minEven, f);
    }
    return maxOdd - minEven;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Remove Duplicates from an Unsorted Linked List Easy
• Two Sum IV - Input is a BST Easy