#3442

Easy

LeetCode Problem Workspace

Maximum Difference Between Even and Odd Frequency I

Find the maximum difference between the frequency of characters in a string with odd and even frequencies.

Problem Statement

You are given a string consisting of lowercase English letters. Your task is to calculate the maximum difference between the frequencies of characters in the string where one frequency is even and the other is odd. The difference is calculated as the absolute difference between the maximum odd frequency and the minimum even frequency.

Return the largest difference between an odd and an even frequency in the given string. Make sure to handle the string's constraints, where at least one character has an odd frequency and one has an even frequency.

Examples

Example 1

Input: s = "aaaaabbc"

Output: 3

Example 2

Input: s = "abcabcab"

Output: 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.

Solution Approach

Build a Frequency Map

Start by constructing a frequency map of characters in the string. Count how many times each character appears, which can be easily done using a hash table.

Identify Odd and Even Frequencies

Once the frequency map is built, separate the frequencies into two categories: odd and even. This step allows you to focus on the specific frequencies relevant to the problem.

Compute the Maximum Difference

Finally, compute the maximum difference by subtracting the minimum even frequency from the maximum odd frequency. This difference represents the largest gap between even and odd frequencies in the string.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(

The time complexity of the solution is O(n), where n is the length of the string, since we traverse the string once to build the frequency map. The space complexity is O(|Σ|), where |Σ| is the number of unique characters in the string, which is at most 26 due to the constraint of lowercase English letters.

What Interviewers Usually Probe

Looking for candidates who can efficiently build a frequency map using a hash table.
Candidates should demonstrate an understanding of the distinction between odd and even frequencies.
Ability to compute the difference between frequencies efficiently is a key signal for success.

Common Pitfalls or Variants

Common pitfalls

Candidates may confuse the calculation of maximum odd and minimum even frequencies.
Forgetting to check both odd and even frequencies could lead to incorrect results.
Candidates might incorrectly handle edge cases where there are multiple odd or even frequencies.

Follow-up variants

Consider a variant where the string contains more than one character with the maximum odd frequency.
Another variant could be calculating the difference for substrings of the string.
A variation could involve returning the difference between any odd and any even frequency, not necessarily the maximum odd and minimum even.

FAQ

How do I calculate the difference between even and odd frequencies in a string?

To calculate the difference, build a frequency map of the string, then find the maximum odd frequency and the minimum even frequency. The difference is the absolute difference between these values.

What data structure is useful for this problem?

A hash table (or dictionary) is ideal for building the frequency map and efficiently accessing character counts.

How can I optimize the solution for this problem?

The solution is already optimal with a time complexity of O(n) and space complexity of O(|Σ|), as we only traverse the string once and store a small frequency map.

What if the string contains no even frequencies?

The problem guarantees at least one even and one odd frequency, so this scenario won't happen.

What is the difference between odd and even frequency in this problem?

Odd frequency refers to character counts that are odd numbers, and even frequency refers to character counts that are even numbers. The goal is to find the largest gap between them.

terminal

Solution

Solution 1: Counting

We can use a hash table or an array $\textit{cnt}$ to record the occurrences of each character in the string $s$. Then, we traverse $\textit{cnt}$ to find the maximum frequency $a$ of characters that appear an odd number of times and the minimum frequency $b$ of characters that appear an even number of times. Finally, we return $a - b$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxDifference(self, s: str) -> int:
        cnt = Counter(s)
        a, b = 0, inf
        for v in cnt.values():
            if v % 2:
                a = max(a, v)
            else:
                b = min(b, v)
        return a - b

Continue Practicing

#3443 maximum manhattan distance after k changes #3438 find valid pair of adjacent digits in string #3389 minimum operations to make character frequencies equal