Maximum Difference Between Even and Odd Frequency | LeetCode

We are given a string consisting of lowercase English letters. Our task is to find the maximum difference between the frequency of two characters in the string such that:

• One of the characters has an even frequency.
• The other character has an odd frequency.

The difference is calculated as: odd_frequency - even_frequency

We need to return the maximum possible difference between the odd and even frequencies.

Example Walkthrough

Let's take a couple of examples to better understand the problem:

Example 1:

Input: s = "aaaaabbc"

Frequencies:

• 'a' → 5 (odd)
• 'b' → 2 (even)
• 'c' → 1 (odd)

Here, the maximum odd frequency is 5 (for 'a') and the maximum even frequency is 2 (for 'b'). Therefore, the result is:

maxOdd - maxEven = 5 - 2 = 3

Example 2:

Input: s = "abcabcab"

Frequencies:

• 'a' → 3 (odd)
• 'b' → 2 (even)
• 'c' → 2 (even)

The maximum odd frequency is 3 (for 'a') and the maximum even frequency is 2 (for 'b' or 'c'). Therefore, the result is:

maxOdd - maxEven = 3 - 2 = 1

Example 3:

Input: s = "mmsmsym"

Frequencies:

• 'm' → 4 (even)
• 's' → 2 (even)
• 'y' → 1 (odd)

The maximum odd frequency is 1 (for 'y') and the minimum even frequency is 2 (for 's'). Therefore, the result is:

maxOdd - minEven = 1 - 2 = -1

Solution Explanation

1. Counting the frequency of each character: We need to find the frequency of each character in the string.
2. Finding the maximum odd and minimum even frequencies: After calculating the frequencies, we must identify the largest odd frequency and the smallest even frequency.
3. Calculating the difference: The result will be the difference between the maximum odd frequency and the minimum even frequency.

Step-by-Step Approach

1. Frequency Calculation: We need to calculate how many times each character appears in the string. We can do this efficiently using an array of size 26 (since there are 26 lowercase English letters). The index of the array corresponds to the character (e.g., index 0 for 'a', index 1 for 'b', etc.).

2. Tracking Odd and Even Frequencies: After counting the frequencies, we need to traverse through the frequency array and find:

   • The maximum odd frequency (i.e., the frequency that is odd and the highest).
   • The minimum even frequency (i.e., the frequency that is even and the smallest).

3. Calculating the Maximum Difference: The difference is calculated as odd_frequency - even_frequency. We return the highest possible difference found.

Code Implementation (C++)

class Solution
{
public:
    int maxDifference(string s)
    {
        vector<int> freq(26, 0);
        for (char c : s)
        {
            freq[c - 'a']++;
        }
        int maxOdd = -1, maxEven = -1, minEven = INT_MAX;
        for (int f : freq)
        {
            if (f % 2 == 1)
            {
                maxOdd = max(maxOdd, f);
            }
            if (f % 2 == 0 && f > 0)
            {
                minEven = min(minEven, f);
                maxEven = max(maxEven, f);
            }
        }
        int result = INT_MIN;
        if (maxOdd != -1 && minEven != INT_MAX)
        {
            result = max(result, maxOdd - minEven);
        }
        return result;
    }
};

Explanation
We initialize a frequency array of size 26 (freq[26]) to store the count of each character.
We iterate through the string and update the frequency of each character.
We then iterate over the frequency array and find:
The maximum odd frequency (maxOdd).
The minimum even frequency (minEven).
The maximum even frequency (maxEven) for possible comparisons.
Finally, we calculate the difference maxOdd - minEven and return it as the result.
Time and Space Complexity
Time Complexity:
Frequency Calculation: Iterating through the string takes O(n), where n is the length of the string.
Frequency Comparison: Iterating through the frequency array of size 26 takes O(26), which is constant time, i.e., O(1).
Thus, the overall time complexity is O(n), where n is the length of the string.
Space Complexity:
We are using a fixed-size array (freq[26]) to store the frequencies of the characters, which requires O(26) space. Since this is a constant size, the space complexity is O(1).
Edge Cases
All characters are the same:
If all characters are the same, there will be only one frequency count, which is either odd or even.
Example: s = "aaaa". The output will be 0 since there are no even and odd frequency pairs.
No valid odd or even frequencies:
The problem guarantees at least one odd and one even frequency, so we don’t need to handle this explicitly.
Large Strings:
The solution works efficiently for large strings up to the constraint of 100 characters due to its linear time complexity.