Skip to main content

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
  1. We initialize a frequency array of size 26 (freq[26]) to store the count of each character.
  2. We iterate through the string and update the frequency of each character.
  3. 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.
  4. 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
  1. 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.
  2. 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.
  3. Large Strings:
    • The solution works efficiently for large strings up to the constraint of 100 characters due to its linear time complexity.

Popular posts from this blog

Maximize Amount After Two Days of Conversions | Leetcode Question

When tackling the problem of maximizing the amount of currency after two days of conversions, we encounter an interesting graph-based problem that involves working with exchange rates between various currencies. In this article, we will explore this problem in detail, starting with the brute force approach and refining it to an optimized solution. Problem Explanation You are given a string initialCurrency (the starting currency), along with four arrays: pairs1 and rates1 : Represent exchange rates between currency pairs on Day 1. pairs2 and rates2 : Represent exchange rates between currency pairs on Day 2. The task is to maximize the amount of initialCurrency you can have after performing any number of conversions on both days. You can make conversions using Day 1 rates and then further conversions using Day 2 rates. Key Insights: Conversion rates are valid (no contradictions). Each currency can be converted back to its counterpart at a reciprocal rate (e.g., if USD -> EUR = 2....
Read more

Final Prices With a Special Discount in a Shop – LeetCode Solution Explained

When tackling coding problems, it's important to understand the problem thoroughly and work through solutions step-by-step. In this blog, we will explore the LeetCode problem "1475 Final Prices With a Special Discount in a Shop" . We'll walk through the problem statement, approach it with a beginner-friendly brute force solution, and analyze its time and space complexity. Finally, we'll discuss any possible optimizations to improve efficiency. Problem Statement You are given an integer array prices where prices[i] represents the price of the i th item in a shop. There is a special discount rule: If you buy the i th item, you receive a discount equal to prices[j] , where j is the smallest index such that j > i and prices[j] <= prices[i] . If no such j exists, you get no discount for that item. Your task is to return a new array answer , where answer[i] is the final price you pay for the i th item after applying the discount. Examples Example 1: Input: p...
Read more