Maximum Difference Between Even and Odd Frequency II solution and explanation
Google
9 more videos on this problem
Maximum Difference Between Even and Odd Frequency II | Super Detailed | Leetcode 3445 | MIKcodestorywithMIK · 1:09:08 · 12K views
Maximum Difference Between Even and Odd Frequency II | Leetcode 3445Techdose · 58:52 · 5K views
Leetcode 3445. Maximum Difference Between Even and Odd Frequency II | Sliding Window + Bitmask 🔥ExpertFunda · 20:06 · 2K views
3445. Maximum Difference Between Even and Odd Frequency II | Leetcode Daily - PythonLeetcode Daily · 8:44 · 1K views
Daily Leetcode #1898: Jun 11, 2025 - 3445. Maximum Difference Between Even and Odd Frequency IIProgramming Live with Larry · 55:13 · 1K views
LeetCode 3445 | Maximum Difference Between Even and Odd Frequency II | Sliding Window + Fenwick TreeAlgoDaily · 28:20 · 962 views
Maximum Difference Between Even and Odd Frequency II (Leetcode Weekly 435)Soumya Bhattacharjee · 14:25 · 651 views
3445. Maximum Difference Between Even and Odd Frequency II (Leetcode Hard)Programming Live with Larry · 1:08:04 · 638 views
3445. Maximum Difference Between Even and Odd Frequency II - LeetCode [Hard] - 11 June 2025Intuit & Code · 50:31 · 394 views
Maximum Difference Between Even and Odd Frequency II | LeetCode 3445 | Java Code | Developer CoderDeveloper Coder · 45:40 · 158 views
The problem
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:
subshas a size of at leastk.- Character
ahas an odd frequency insubs. - Character
bhas a non-zero even frequency insubs.
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 * 104sconsists 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
subsis at leastk. - The number of occurrences of character
ainsubsis odd. - The number of occurrences of character
binsubsis even. - Maximize the frequency difference
f_a - f_b, wheref_aandf_bare the number of occurrences ofaandbinsubs, 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
ais the target character with odd frequency. - Character
bis the target character with even frequency.
We use a sliding window to maintain the left and right boundaries of the substring, with variables:
ldenotes the position before the left boundary, so the window is[l+1, r];ris the right boundary, traversing the entire string;curAandcurBdenote the number of occurrences ofaandbin the current window;preAandpreBdenote the cumulative occurrences ofaandbbefore the left boundaryl.
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)$.
class Solution:
def maxDifference(self, S: str, k: int) -> int:
s = list(map(int, S))
ans = -inf
for a in range(5):
for b in range(5):
if a == b:
continue
curA = curB = 0
preA = preB = 0
t = [[inf, inf], [inf, inf]]
l = -1
for r, x in enumerate(s):
curA += x == a
curB += x == b
while r - l >= k and curB - preB >= 2:
t[preA & 1][preB & 1] = min(t[preA & 1][preB & 1], preA - preB)
l += 1
preA += s[l] == a
preB += s[l] == b
ans = max(ans, curA - curB - t[curA & 1 ^ 1][curB & 1])
return ansclass Solution {
public int maxDifference(String S, int k) {
char[] s = S.toCharArray();
int n = s.length;
final int inf = Integer.MAX_VALUE / 2;
int ans = -inf;
for (int a = 0; a < 5; ++a) {
for (int b = 0; b < 5; ++b) {
if (a == b) {
continue;
}
int curA = 0, curB = 0;
int preA = 0, preB = 0;
int[][] t = {{inf, inf}, {inf, inf}};
for (int l = -1, r = 0; r < n; ++r) {
curA += s[r] == '0' + a ? 1 : 0;
curB += s[r] == '0' + b ? 1 : 0;
while (r - l >= k && curB - preB >= 2) {
t[preA & 1][preB & 1] = Math.min(t[preA & 1][preB & 1], preA - preB);
++l;
preA += s[l] == '0' + a ? 1 : 0;
preB += s[l] == '0' + b ? 1 : 0;
}
ans = Math.max(ans, curA - curB - t[curA & 1 ^ 1][curB & 1]);
}
}
}
return ans;
}
}class Solution {
public:
int maxDifference(string s, int k) {
const int n = s.size();
const int inf = INT_MAX / 2;
int ans = -inf;
for (int a = 0; a < 5; ++a) {
for (int b = 0; b < 5; ++b) {
if (a == b) {
continue;
}
int curA = 0, curB = 0;
int preA = 0, preB = 0;
int t[2][2] = {{inf, inf}, {inf, inf}};
int l = -1;
for (int r = 0; r < n; ++r) {
curA += (s[r] == '0' + a);
curB += (s[r] == '0' + b);
while (r - l >= k && curB - preB >= 2) {
t[preA & 1][preB & 1] = min(t[preA & 1][preB & 1], preA - preB);
++l;
preA += (s[l] == '0' + a);
preB += (s[l] == '0' + b);
}
ans = max(ans, curA - curB - t[(curA & 1) ^ 1][curB & 1]);
}
}
}
return ans;
}
};function maxDifference(S: string, k: number): number {
const s = S.split('').map(Number);
let ans = -Infinity;
for (let a = 0; a < 5; a++) {
for (let b = 0; b < 5; b++) {
if (a === b) {
continue;
}
let [curA, curB, preA, preB] = [0, 0, 0, 0];
const t: number[][] = [
[Infinity, Infinity],
[Infinity, Infinity],
];
let l = -1;
for (let r = 0; r < s.length; r++) {
const x = s[r];
curA += x === a ? 1 : 0;
curB += x === b ? 1 : 0;
while (r - l >= k && curB - preB >= 2) {
t[preA & 1][preB & 1] = Math.min(t[preA & 1][preB & 1], preA - preB);
l++;
preA += s[l] === a ? 1 : 0;
preB += s[l] === b ? 1 : 0;
}
ans = Math.max(ans, curA - curB - t[(curA & 1) ^ 1][curB & 1]);
}
}
}
return ans;
}func maxDifference(s string, k int) int {
n := len(s)
inf := math.MaxInt32 / 2
ans := -inf
for a := 0; a < 5; a++ {
for b := 0; b < 5; b++ {
if a == b {
continue
}
curA, curB := 0, 0
preA, preB := 0, 0
t := [2][2]int{{inf, inf}, {inf, inf}}
l := -1
for r := 0; r < n; r++ {
if s[r] == byte('0'+a) {
curA++
}
if s[r] == byte('0'+b) {
curB++
}
for r-l >= k && curB-preB >= 2 {
t[preA&1][preB&1] = min(t[preA&1][preB&1], preA-preB)
l++
if s[l] == byte('0'+a) {
preA++
}
if s[l] == byte('0'+b) {
preB++
}
}
ans = max(ans, curA-curB-t[curA&1^1][curB&1])
}
}
}
return ans
}use std::cmp::{max, min};
use std::i32::{MAX, MIN};
impl Solution {
pub fn max_difference(S: String, k: i32) -> i32 {
let s: Vec<usize> = S.chars().map(|c| c.to_digit(10).unwrap() as usize).collect();
let k = k as usize;
let mut ans = MIN;
for a in 0..5 {
for b in 0..5 {
if a == b {
continue;
}
let mut curA = 0;
let mut curB = 0;
let mut preA = 0;
let mut preB = 0;
let mut t = [[MAX; 2]; 2];
let mut l: isize = -1;
for (r, &x) in s.iter().enumerate() {
curA += (x == a) as i32;
curB += (x == b) as i32;
while (r as isize - l) as usize >= k && curB - preB >= 2 {
let i = (preA & 1) as usize;
let j = (preB & 1) as usize;
t[i][j] = min(t[i][j], preA - preB);
l += 1;
if l >= 0 {
preA += (s[l as usize] == a) as i32;
preB += (s[l as usize] == b) as i32;
}
}
let i = (curA & 1 ^ 1) as usize;
let j = (curB & 1) as usize;
if t[i][j] != MAX {
ans = max(ans, curA - curB - t[i][j]);
}
}
}
}
ans
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n^3) | O(1) | Educational baseline to understand the problem constraints and parity checks |
| Prefix Frequency + Pair Enumeration | O(26^2 · n) | O(26 · n) | When you want faster substring frequency queries using prefix sums |
| Pair Enumeration + Sliding Window + Prefix State Compression | O(26^2 · n) | O(n) | Optimal approach for large inputs; combines prefix difference tracking with parity states |
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.