Maximum Difference Between Even and Odd Frequency I

EASY

Description

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

Checkout 2 different approaches to solve Maximum Difference Between Even and Odd Frequency I. Click on different approaches to view the approach and algorithm in detail.

Brute-Force on Frequencies

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.

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.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int maxDifference(String s) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        List<Integer> oddFrequencies = new ArrayList<>();
        List<Integer> evenFrequencies = new ArrayList<>();

        for (int freq : freqMap.values()) {
            if (freq % 2 != 0) {
                oddFrequencies.add(freq);
            } else {
                evenFrequencies.add(freq);
            }
        }

        int maxDifference = Integer.MIN_VALUE;
        for (int oddFreq : oddFrequencies) {
            for (int evenFreq : evenFrequencies) {
                maxDifference = Math.max(maxDifference, oddFreq - evenFreq);
            }
        }

        return maxDifference;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Maximum Difference Between Even and Odd Frequency I. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Maximum Difference Between Even and Odd Frequency I

Patterns:

Counting

Data Structures:

Hash TableString