Maximum Difference Between Even and Odd Frequency I Python/Java solution

Most implementations use a dictionary or array to count characters, then scan the counts to find the largest odd and smallest even values. The logic is identical across Python, Java, C++, Go, and TypeScript, differing only in syntax for maps and loops.

How to solve Maximum Difference Between Even and Odd Frequency I in O(n)?

First count the frequency of each character in the string using an array or hash map. Then iterate through those counts and track two values: the largest odd frequency and the smallest even frequency. Compute their difference if both exist. Each step scans the data once, giving O(n) overall complexity.

What is the best approach for Maximum Difference Between Even and Odd Frequency I?

The best approach is frequency counting with extreme tracking. Count occurrences of each character, then find the maximum odd frequency and the minimum even frequency. The final answer is maxOdd - minEven. This runs in O(n) time with O(k) space, where k is the number of unique characters.

Is Maximum Difference Between Even and Odd Frequency I asked at Google/Amazon/Meta?

Frequency counting and parity-based string problems are common in interviews at companies like Amazon, Google, and Meta. While this exact question may not appear frequently, the underlying pattern—counting characters and comparing frequency properties—is a standard interview topic.

What data structure is used in Maximum Difference Between Even and Odd Frequency I?

The main data structure is a hash table or fixed-size frequency array. It stores the count of each character in the string. After counting, simple variables track the maximum odd and minimum even frequencies.

What is the time complexity of Maximum Difference Between Even and Odd Frequency I?

The optimal solution runs in O(n + k) time. n is the length of the string used to build the frequency map, and k is the number of unique characters scanned to find the maximum odd and minimum even frequencies. Space complexity is O(k).

Description Hints 1 Solution Video 6:30

3442. Maximum Difference Between Even and Odd Frequency I

Q: Is Maximum Difference Between Even and Odd Frequency I easy or hard?

Maximum Difference Between Even and Odd Frequency I is categorized as an Easy problem. The main concept is basic frequency counting on strings and checking whether counts are odd or even, which is a common beginner-friendly interview pattern.

Easy60.7% acceptance4 companies

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.

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.

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.

Asked at 4 companies

Microsoft

Google Amazon Meta

Topics

Hints open one at a time

Hint 1

Use a frequency map to identify the maximum odd and minimum even frequencies. Then, calculate their difference.

6:30

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxDifference(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"aaaaabbc"

Input

"abcabcab"

Your code is saved on this device.Solution