Maximum Difference Between Even and Odd Frequency I

Maximum Difference Between Even and Odd Frequency I - Problem

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.

Input & Output

Example 1 — Mixed Frequencies

$ Input: s = "aabbbcc"

› Output: 1

💡 Note: Frequencies: a=2 (even), b=3 (odd), c=2 (even). Max odd frequency is 3, min even frequency is 2. Difference = 3 - 2 = 1.

Example 2 — All Even Frequencies

$ Input: s = "abab"

› Output: 0

💡 Note: Frequencies: a=2 (even), b=2 (even). No odd frequencies exist, so we cannot form the required difference. Return 0.

Example 3 — Single Character

$ Input: s = "a"

› Output: 0

💡 Note: Frequency: a=1 (odd). Only odd frequency exists, no even frequencies to subtract from. Return 0.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input String

String with repeating characters

Count Frequencies

Count each character's frequency and categorize as odd/even

Find Maximum Difference

Max odd frequency minus min even frequency

Key Takeaway

🎯 Key Insight: Find the character with maximum odd frequency and subtract the character with minimum even frequency to get the maximum possible difference.

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to find the maximum difference between any odd frequency character and any even frequency character. The optimal approach counts character frequencies in O(n) time and tracks the maximum odd frequency and minimum even frequency. Best approach: Single pass frequency counting with simultaneous max/min tracking. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ One-Pass Optimal Solution	O(n)	O(k)	Single pass counting with simultaneous tracking of max odd and min even frequencies
Brute Force Frequency Comparison	O(n + k²)	O(k)	Count all frequencies, then compare every odd frequency against every even frequency
Two-Pass Frequency Count	O(n + k)	O(k)	First pass counts frequencies, second pass finds max odd and min even

One-Pass Optimal Solution — Algorithm Steps

Initialize max_odd = -1 and min_even = infinity
Count character frequencies while updating max_odd and min_even
Return max_odd - min_even if both exist, otherwise 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Count & Track

Count frequencies while tracking max odd and min even

Final State

After processing all characters

Calculate Result

Return max_odd - min_even

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(char* s) {
    int freq[26] = {0};
    int len = strlen(s);
    
    // Count all frequencies
    for (int i = 0; i < len; i++) {
        freq[s[i] - 'a']++;
    }
    
    int maxOdd = -1;
    int minEven = INT_MAX;
    
    // Find max odd and min even
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            if (freq[i] % 2 == 1) {
                if (freq[i] > maxOdd) {
                    maxOdd = freq[i];
                }
            } else {
                if (freq[i] < minEven) {
                    minEven = freq[i];
                }
            }
        }
    }
    
    // If no odd or no even frequencies found
    if (maxOdd == -1 || minEven == INT_MAX) {
        return 0;
    }
    
    return (maxOdd - minEven > 0) ? maxOdd - minEven : 0;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string to count and track frequencies simultaneously

✓ Linear Growth

Space Complexity

O(k)

Hash map stores at most 26 character frequencies

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

One-Pass Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler