Maximum Difference Between Even and Odd Frequency I

Easy

#3059Time: O(N + K^2), where N is the length of the string and K is the number of unique characters (at most 26). - O(N) to iterate through the string and build the frequency map. - O(K) to populate the odd and even frequency lists. - O(K_odd * K_even) for the nested loops, which is O(K^2) in the worst case. Since K is a constant (26), the overall complexity is dominated by the initial string traversal, making it effectively O(N). However, it's conceptually less efficient due to the nested loops.Space: O(K), where K is the number of unique characters (at most 26). This space is used for the frequency map and the two lists to store odd and even frequencies. Since K is constant, this is considered O(1) space.

Patterns

Counting

Data structures

Hash Table String

Prompt

You are given a string s consisting of lowercase English letters.

Your task is to find the maximum difference diff = freq(a₁) - freq(a₂) between the frequency of characters a₁ and a₂ in the string such that:

a₁ has an odd frequency in the string.
a₂ has 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 of 5, and 'b' has an even frequency of 2.
The maximum difference is 5 - 2 = 3.

Example 2:

Input: s = "abcabcab"

Output: 1

Explanation:

The character 'a' has an odd frequency of 3, and 'c' has an even frequency of 2.
The maximum difference is 3 - 2 = 1.

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach first calculates the frequency of each character. Then, it separates the characters into two groups: those with odd frequencies and those with even frequencies. Finally, it iterates through all possible pairs of one character from the odd-frequency group and one from the even-frequency group to find the maximum possible difference.

Algorithm

Create a frequency map (e.g., a HashMap or an array of size 26) to store the counts of each character in the string s.
Iterate through the string s to populate the frequency map.
Create two lists: oddFrequencies and evenFrequencies.
Iterate through the values in the frequency map. If a frequency is non-zero, add it to the oddFrequencies list if it's odd, or to the evenFrequencies list if it's even.
Initialize a variable maxDifference to a very small number (e.g., Integer.MIN_VALUE).
Use nested loops to iterate through every frequency oddFreq in oddFrequencies and every frequency evenFreq in evenFrequencies.
For each pair, calculate the difference oddFreq - evenFreq and update maxDifference if this difference is larger.
Return maxDifference.

Walkthrough

To solve the problem, we can start by counting how many times each character appears in the string. A hash map is a suitable data structure for this. After counting, we can segregate the frequencies into two separate lists: one for odd frequencies and one for even frequencies. To find the maximum difference, we need to find an odd frequency a1 and an even frequency a2 such that a1 - a2 is maximized. This is equivalent to finding the largest value in the oddFrequencies list and the smallest value in the evenFrequencies list. This brute-force method checks every possible pair of an odd frequency and an even frequency to find this maximum difference.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class Solution {7    public int maxDifference(String s) {8        Map<Character, Integer> freqMap = new HashMap<>();9        for (char c : s.toCharArray()) {10            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);11        }12 13        List<Integer> oddFrequencies = new ArrayList<>();14        List<Integer> evenFrequencies = new ArrayList<>();15 16        for (int freq : freqMap.values()) {17            if (freq % 2 != 0) {18                oddFrequencies.add(freq);19            } else {20                evenFrequencies.add(freq);21            }22        }23 24        int maxDifference = Integer.MIN_VALUE;25        for (int oddFreq : oddFrequencies) {26            for (int evenFreq : evenFrequencies) {27                maxDifference = Math.max(maxDifference, oddFreq - evenFreq);28            }29        }30 31        return maxDifference;32    }33}

Complexity

Time

O(N + K^2), where N is the length of the string and K is the number of unique characters (at most 26). - O(N) to iterate through the string and build the frequency map. - O(K) to populate the odd and even frequency lists. - O(K_odd * K_even) for the nested loops, which is O(K^2) in the worst case. Since K is a constant (26), the overall complexity is dominated by the initial string traversal, making it effectively O(N). However, it's conceptually less efficient due to the nested loops.

Space

O(K), where K is the number of unique characters (at most 26). This space is used for the frequency map and the two lists to store odd and even frequencies. Since K is constant, this is considered O(1) space.

Trade-offs

Pros

Simple to understand and implement.
Correctly solves the problem.

Cons

Less efficient than the optimal approach due to the nested loops that check all pairs of odd and even frequencies, which is unnecessary.

This is the most efficient approach. It recognizes that to maximize the difference freq(a1) - freq(a2), we only need the maximum odd frequency and the minimum even frequency. The approach first calculates all character frequencies in a single pass. Then, in a second pass over the frequencies, it finds the maximum odd frequency and the minimum even frequency simultaneously.

Algorithm

Initialize an integer array frequencies of size 26 to all zeros. This array will map each lowercase letter to its frequency.
Iterate through the input string s. For each character c, increment the count at frequencies[c - 'a'].
Initialize two variables: maxOddFreq to a very small number (e.g., Integer.MIN_VALUE) and minEvenFreq to a very large number (e.g., Integer.MAX_VALUE).
Iterate through the frequencies array from index 0 to 25.
For each frequency freq in the array that is greater than 0:
- If freq is odd, update maxOddFreq = Math.max(maxOddFreq, freq).
- If freq is even, update minEvenFreq = Math.min(minEvenFreq, freq).
The problem guarantees that at least one character with an odd frequency and one with an even frequency exist, so maxOddFreq and minEvenFreq will be updated correctly.
Return the final result: maxOddFreq - minEvenFreq.

Walkthrough

To maximize the expression freq(a1) - freq(a2), where freq(a1) is odd and freq(a2) is even, we should choose the largest possible odd frequency and the smallest possible even frequency. This insight allows us to avoid comparing all pairs.

The algorithm proceeds as follows:

First, we count the frequency of each character. Since the input consists only of lowercase English letters, a simple array of size 26 is sufficient and efficient for this task.
We then iterate through this frequency array. We maintain two variables: maxOddFreq to track the largest odd frequency seen so far, and minEvenFreq to track the smallest even frequency seen so far.
During the iteration, if we encounter an odd frequency, we compare it with maxOddFreq and update if it's larger. If we encounter an even frequency, we compare it with minEvenFreq and update if it's smaller.
After checking all character frequencies, the final answer is simply maxOddFreq - minEvenFreq.

1class Solution {2    public int maxDifference(String s) {3        int[] frequencies = new int[26];4        for (char c : s.toCharArray()) {5            frequencies[c - 'a']++;6        }7 8        int maxOddFreq = Integer.MIN_VALUE;9        int minEvenFreq = Integer.MAX_VALUE;10 11        for (int freq : frequencies) {12            if (freq == 0) {13                continue; // Skip characters not present in the string14            }15            if (freq % 2 != 0) { // Odd frequency16                maxOddFreq = Math.max(maxOddFreq, freq);17            } else { // Even frequency18                minEvenFreq = Math.min(minEvenFreq, freq);19            }20        }21 22        // The problem guarantees both types of frequencies exist.23        return maxOddFreq - minEvenFreq;24    }25}

Complexity

Time

O(N), where N is the length of the string. - O(N) to iterate through the string and populate the frequency array. - O(K) to iterate through the frequency array, where K is the alphabet size (26). The total time complexity is O(N + K). Since K is a constant, this simplifies to O(N).

Space

O(1). We use a fixed-size array of 26 integers to store frequencies, which does not depend on the input string size. Therefore, the space complexity is constant.

Trade-offs

Pros

Highly efficient in both time and space.
Solves the problem in a single pass over the frequencies after the initial count.
Avoids unnecessary comparisons by directly targeting the maximum odd and minimum even frequencies.

Cons

No significant cons; this is the optimal solution for the given constraints.

Solutions

Solution

1public class Solution {2    public int MaxDifference(string s) {3        int[] cnt = new int[26];4        foreach(char c in s) {5            ++cnt[c - 'a'];6        }7        int a = 0, b = 1 << 30;8        foreach(int v in cnt) {9            if (v % 2 == 1) {10                a = Math.Max(a, v);11            } else if (v > 0) {12                b = Math.Min(b, v);13            }14        }15        return a - b;16    }17}

1class Solution {2public3  int maxDifference(String s) {4    int[] cnt = new int[26];5    for (char c : s.toCharArray()) {6      ++cnt[c - 'a'];7    }8    int a = 0, b = 1 << 30;9    for (int v : cnt) {10      if (v % 2 == 1) {11        a = Math.max(a, v);12      } else if (v > 0) {13        b = Math.min(b, v);14      }15    }16    return a - b;17  }18}

1class Solution {2public:3  int maxDifference(string s) {4    int cnt[26]{};5    for (char c : s) {6      ++cnt[c - 'a'];7    }8    int a = 0, b = 1 << 30;9    for (int v : cnt) {10      if (v % 2 == 1) {11        a = max(a, v);12      } else if (v > 0) {13        b = min(b, v);14      }15    }16    return a - b;17  }18};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem