Skip to main content
Talentd

Maximum Difference Between Even and Odd Frequency II - Solution & Explanation

HardStringSliding WindowEnumerationPrefix Sum17 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

You are given a string s and an integer k. Your task is to find the maximum difference between the frequency of two characters, freq[a] - freq[b], in a substring subs of s, such that:

  • subs has a size of at least k.
  • Character a has an odd frequency in subs.
  • Character b has a non-zero even frequency in subs.

Return the maximum difference.

Note that subs can contain more than 2 distinct characters.

 

Example 1:

Input: s = "12233", k = 4

Output: -1

Explanation:

For the substring "12233", the frequency of '1' is 1 and the frequency of '3' is 2. The difference is 1 - 2 = -1.

Example 2:

Input: s = "1122211", k = 3

Output: 1

Explanation:

For the substring "11222", the frequency of '2' is 3 and the frequency of '1' is 2. The difference is 3 - 2 = 1.

Example 3:

Input: s = "110", k = 3

Output: -1

 

Constraints:

  • 3 <= s.length <= 3 * 104
  • s consists only of digits '0' to '4'.
  • The input is generated that at least one substring has a character with an even frequency and a character with an odd frequency.
  • 1 <= k <= s.length

Approach Overview

Problem Overview: Given a string, you need the maximum difference between the frequency of a character with odd count and another character with even count inside a valid substring. The challenge is enforcing the parity constraints while scanning substrings efficiently without checking every possible range.

Approach 1: Brute Force Substring Enumeration (O(n^3) time, O(1) space)

Generate every possible substring and compute the frequency of characters inside it. For each substring, check all character pairs and compute oddFreq - evenFreq when one frequency is odd and the other is even. Frequency counting requires scanning the substring or maintaining counts, and checking pairs adds another loop. This approach works only for very small inputs because substring enumeration already costs O(n^2), and verifying frequency conditions pushes the complexity close to O(n^3).

Approach 2: Prefix Frequency + Pair Enumeration (O(26^2 · n) time, O(26 · n) space)

Instead of recomputing counts for every substring, precompute prefix frequency arrays. With prefix sums, the count of any character in a substring can be obtained in O(1). Then enumerate ordered character pairs (a, b) where a represents the odd-frequency candidate and b the even-frequency candidate. For each pair, iterate through the string and derive counts using prefix differences. This reduces repeated counting but still requires scanning the string for every pair.

Approach 3: Character Pair Enumeration + Sliding Window + Prefix State Compression (O(26^2 · n) time, O(n) space)

The optimized solution fixes a pair of characters (a, b) and scans the string once using prefix differences and parity states. Maintain running counts for both characters and track whether their frequencies are odd or even. A compressed prefix state represents the parity combination seen so far. Using a technique similar to prefix sums with state tracking, you store the minimum prefix difference for each parity state and update the answer while expanding the window. This effectively converts the substring constraint into a difference of prefix states.

Enumeration over all character pairs ensures every valid odd/even combination is considered, while the linear scan ensures each pair is processed in O(n). The approach relies on ideas from sliding window, prefix sum, and enumeration to avoid explicit substring generation.

Recommended for interviews: The character pair enumeration with sliding window and prefix state compression is the expected solution. Mentioning the brute force first shows you understand the search space. Transitioning to prefix differences and parity states demonstrates the optimization interviewers look for in hard string problems.

Solution

We want to find a substring subs of string s that satisfies the following conditions:

  • The length of subs is at least k.
  • The number of occurrences of character a in subs is odd.
  • The number of occurrences of character b in subs is even.
  • Maximize the frequency difference f_a - f_b, where f_a and f_b are the number of occurrences of a and b in subs, respectively.

The characters in s are from '0' to '4', so there are 5 possible characters. We can enumerate all different character pairs (a, b), for a total of at most 5 times 4 = 20 combinations. We define:

  • Character a is the target character with odd frequency.
  • Character b is the target character with even frequency.

We use a sliding window to maintain the left and right boundaries of the substring, with variables:

  • l denotes the position before the left boundary, so the window is [l+1, r];
  • r is the right boundary, traversing the entire string;
  • curA and curB denote the number of occurrences of a and b in the current window;
  • preA and preB denote the cumulative occurrences of a and b before the left boundary l.

We use a 2D array t[2][2] to record the minimum value of preA - preB for each possible parity combination of the window's left end, where t[i][j] means preA bmod 2 = i and preB bmod 2 = j.

Each time we move r to the right, if the window length satisfies r - l \ge k and curB - preB \ge 2, we try to move the left boundary l to shrink the window, and update the corresponding t[preA bmod 2][preB bmod 2].

Then, we try to update the answer:

$ ans = max(ans,\ curA - curB - t[(curA bmod 2) \oplus 1][curB bmod 2])

In this way, we can compute the maximum frequency difference for the current window each time r moves to the right.

The time complexity is O(n times |\Sigma|^2), where n is the length of s and |\Sigma| is the alphabet size (5 in this problem). The space complexity is O(1)$.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring EnumerationO(n^3)O(1)Educational baseline to understand the problem constraints and parity checks
Prefix Frequency + Pair EnumerationO(26^2 · n)O(26 · n)When you want faster substring frequency queries using prefix sums
Pair Enumeration + Sliding Window + Prefix State CompressionO(26^2 · n)O(n)Optimal approach for large inputs; combines prefix difference tracking with parity states

Video Solution

Maximum Difference Between Even and Odd Frequency II | Super Detailed | Leetcode 3445 | MIK • codestorywithMIK • 12,374 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Difference Between Even and Odd Frequency II easy or hard?
Maximum Difference Between Even and Odd Frequency II is categorized as Hard. The difficulty comes from combining multiple techniques: pair enumeration, prefix sum transformations, parity reasoning, and optimized scanning to avoid checking every substring.
Maximum Difference Between Even and Odd Frequency II Python/Java solution
Implementations typically enumerate character pairs and maintain running prefix counts while scanning the string. Python, Java, C++, Go, and TypeScript versions all follow the same logic: compute prefix differences, track parity states, and update the maximum difference when a valid state combination appears.
How to solve Maximum Difference Between Even and Odd Frequency II in O(n)?
The string itself cannot be solved in strict O(n) because the algorithm must consider pairs of characters. However, each pair can be processed in O(n) time using prefix differences and parity states. Enumerating all pairs results in O(26^2 · n), which is effectively linear for a fixed alphabet.
What is the best approach for Maximum Difference Between Even and Odd Frequency II?
The most efficient approach enumerates character pairs and scans the string using prefix differences with parity state compression. For each pair (a, b), maintain prefix counts and track parity states while sliding through the string. This reduces substring checking to prefix comparisons and runs in O(26^2 · n) time with O(n) space.
Is Maximum Difference Between Even and Odd Frequency II asked at Google/Amazon/Meta?
Problems combining prefix sums, sliding window, and parity constraints are common in interviews at companies like Google, Amazon, and Meta. Hard string problems that require state compression or prefix transformations are especially popular in senior or onsite interview rounds.
What data structure is used in Maximum Difference Between Even and Odd Frequency II?
The solution primarily uses prefix frequency arrays, parity state tracking, and hash maps or arrays to store the best prefix state seen so far. These structures allow constant-time substring frequency checks and efficient updates during the sliding scan.
What is the time complexity of Maximum Difference Between Even and Odd Frequency II?
The optimal solution runs in O(26^2 · n) time because every ordered pair of characters is processed once and the string is scanned linearly for each pair. The space complexity is O(n) for storing prefix states or compressed state information used during the scan.

Ready to solve this problem?

Practice Maximum Difference Between Even and Odd Frequency II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Elements With Maximum Frequency

Next

Frequency of the Most Frequent Element