#3445

Hard

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Maximum Difference Between Even and Odd Frequency II

Find the maximum difference between even and odd character frequencies in substrings using sliding window updates efficiently.

string sliding window enumeration prefix sum

Problem Statement

Given a string s of digits '0' to '4' and an integer k, find the maximum difference freq[a] - freq[b] for any substring of length k where freq[a] and freq[b] correspond to two characters in the substring, one with even frequency and the other with odd frequency. Substrings may contain more than two distinct characters, but only the two fixed characters are considered for the difference.

Return the maximum possible difference across all valid substrings. For example, with s = "12233" and k = 4, the substring "1223" has '1' with frequency 1 and '3' with frequency 2, resulting in a difference of -1. Constraints: 3 <= s.length <= 30000, 1 <= k <= s.length, and there is always at least one substring meeting the even/odd frequency condition.

Examples

Example 1

Input: s = "12233", k = 4

Output: -1

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

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

Example details omitted.

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

Solution Approach

Fix two characters and iterate

Enumerate all pairs of characters from '0' to '4' and treat each pair as candidates for freq[a] and freq[b]. Only consider these two characters when computing frequency differences, ignoring others.

Sliding window frequency update

Maintain a sliding window of size k, updating counts of the two fixed characters as you slide. Incrementally adjust counts instead of recomputing from scratch to improve efficiency.

Track even and odd differences

For each window, check if one character has even frequency and the other odd, then compute freq[a] - freq[b]. Keep a running maximum across all windows and all character pairs.

Complexity Analysis

Metric	Value
Time	O(n\times
Space	O(1)

Time complexity is O(n * |Σ|^2) since we consider all pairs of characters and slide the window over n elements. Space complexity is O(1) because only counts for two characters are maintained, independent of input size.

What Interviewers Usually Probe

Expect candidates to fix two characters to reduce the problem scope.
Look for efficient sliding window implementation rather than recomputation per substring.
Check understanding of even vs odd frequency tracking within a running window.

Common Pitfalls or Variants

Common pitfalls

Forgetting that substrings can contain more than two characters while only comparing the selected pair.
Recomputing frequencies from scratch on every window, causing timeouts.
Incorrectly handling even and odd frequency checks when frequencies are zero.

Follow-up variants

Compute maximum difference where substrings must contain exactly two distinct characters.
Find maximum difference considering all characters, not fixing pairs in advance.
Adjust the problem for strings with larger digit ranges, e.g., '0'-'9'.

FAQ

What is the core pattern for Maximum Difference Between Even and Odd Frequency II?

The core pattern is sliding window with running state updates while fixing two characters and tracking their even and odd frequencies.

Why do we fix two characters at a time?

Fixing two characters simplifies frequency difference calculation and prevents recomputation for unrelated characters.

Can substrings have more than two distinct characters?

Yes, but only the two selected characters are used to compute the difference; others are ignored.

How do you efficiently update counts in the sliding window?

Increment or decrement counts for the two characters as the window moves instead of recalculating for the entire window.

What causes common timeouts in this problem?

Recomputing frequencies for all characters on each window rather than using a running count leads to inefficient O(n*k) solutions.

terminal

Solution

Solution 1: Enumerate Character Pairs + Sliding Window + Prefix State Compression

We want to find a substring $\textit{subs}$ of string $s$ that satisfies the following conditions:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

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 ans

Continue Practicing

#3261 count substrings that satisfy k constraint ii #3234 count the number of substrings with dominant ones #2947 count beautiful substrings i