Problem Statement

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

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

• a1 has an odd frequency in the string.
• a2 has an even frequency in the string.

Return this maximum difference.

LeetCode Links:

Maximum Difference Between Even and Odd Frequency I

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.

Examples

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.

Different Approaches

1️⃣ Brute Force Approach (Inefficient)

✔️ Idea:

• For each character, count frequency manually.
• Check if even/odd and update max/min accordingly.

🧠 Intuition:

• For every character ch in the alphabet (a to z):
  • Count how many times it appears in the string s.
  • If it's odd, update maxOdd.
  • If it's even, update minEven.
• Finally, return maxOdd - minEven, or 0 if either is missing

Code:

#include <iostream>
#include <string>
#include <climits>
using namespace std;

class Solution {
public:
    int maxDifference(string s) {
        int maxOdd = 0;
        int minEven = INT_MAX;

        for (char ch = 'a'; ch <= 'z'; ++ch) {
            int count = 0;
            for (char c : s) {
                if (c == ch) count++;
            }

            if (count == 0) continue;

            if (count % 2 == 0) {
                minEven = min(minEven, count);
            } else {
                maxOdd = max(maxOdd, count);
            }
        }

        if (maxOdd == 0 || minEven == INT_MAX) return 0;
        return maxOdd - minEven;
    }
};

int main() {
    Solution sol;
    string s = "aabbcccddde";
    cout << "Result: " << sol.maxDifference(s) << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(26 * n)
  • Outer loop: Iterates 26 time (once for each lowercase letter from a to z)
  • Inner loop: Iterates n times (length of string)
  • Total: O(n) * O(26) = O(26 n) = O(n)
• Space Complexity:O(1)

2️⃣ Using Frequency Array

✔️ Idea:

• Count frequency of each character using a size-26 array.
• Track:
  • maxOdd: maximum of all odd frequencies.
  • minEven: minimum of all even frequencies.

🧾 C++ Code:

class Solution {
public:
    int maxDifference(string s) {
        int freq[26] = {0};
        for (char ch : s) {
            freq[ch - 'a']++;
        }

        int maxOdd = 0;
        int minEven = INT_MAX;

        for (int i = 0; i < 26; i++) {
            if (freq[i] == 0) continue;
            if (freq[i] % 2 == 0) {
                minEven = min(minEven, freq[i]);
            } else {
                maxOdd = max(maxOdd, freq[i]);
            }
        }

        if (maxOdd == 0 || minEven == INT_MAX) return 0;
        return maxOdd - minEven;
    }
};

Complexity Analysis:

• Time Complexity:O(n + 26) = O(n)
  • n is the length of the string s
  • 26 for iterating over character frequencies
• Space Complexity:
  • O(1): Using fixed-size array of 26

3️⃣ Using Hash Map

Idea:

• Use unordered_map<char, int> to support any character set (like Unicode).
• Otherwise, logic is the same.

Code:

class Solution {
public:
    int maxDifference(string s) {
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }

        int maxOdd = 0;
        int minEven = INT_MAX;

        for (auto& [ch, f] : freq) {
            if (f % 2 == 0)
                minEven = min(minEven, f);
            else
                maxOdd = max(maxOdd, f);
        }

        if (maxOdd == 0 || minEven == INT_MAX) return 0;
        return maxOdd - minEven;
    }
};

Complexity Analysis:

• Time Complexity: O(n)
  • O(n): for frequency counting
  • O(k): where k is number of distinct characters (at most 26 for lowercase)
  • Total: O(n)
• Space Complexity: O(k)
  • O(k): for hash map