# Maximum Difference Between Even and Odd Frequency II
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-difference-between-even-and-odd-frequency-ii)
Canonical: https://scaleengineer.com/dsa/problems/maximum-difference-between-even-and-odd-frequency-ii
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** String
---
## 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:

* `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`

# Approaches
## Brute Force
The brute-force approach is the most straightforward way to solve the problem. It involves systematically checking every possible substring of the input string `s`, verifying if it meets the given criteria, and then calculating the potential difference to update a global maximum.
**Time:** O(N³), where N is the length of the string. There are O(N²) substrings, and for each, we iterate up to N times to calculate frequencies. This is too slow for the given constraints. · **Space:** O(1), as the frequency map size is constant (5 for digits '0'-'4').
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error on platforms with typical time limits for the given constraints.
### Explanation
This method iterates through all possible start and end indices, `i` and `j`, to define a substring. For each substring, it first checks if its length is at least `k`. If it is, the algorithm then computes the frequency of each character within that specific substring. This is done by iterating through the substring's characters and using an array to store counts. Once the frequencies are known, it searches for a character `a` with an odd frequency and a character `b` with a non-zero, even frequency. For every such valid pair `(a, b)`, it calculates `freq[a] - freq[b]` and updates the overall maximum difference found so far. This process is repeated for all substrings of length `k` or more.

```java
class Solution {
    public int maxDiff(String s, int k) {
        int n = s.length();
        int maxDifference = Integer.MIN_VALUE;
        boolean found = false;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (j - i + 1 < k) {
                    continue;
                }

                int[] freq = new int[5];
                for (int l = i; l <= j; l++) {
                    freq[s.charAt(l) - '0']++;
                }

                int maxOddFreq = -1;
                int minEvenFreq = Integer.MAX_VALUE;
                boolean hasOdd = false;
                boolean hasEven = false;

                for (int charIdx = 0; charIdx < 5; charIdx++) {
                    if (freq[charIdx] > 0) {
                        if (freq[charIdx] % 2 != 0) {
                            maxOddFreq = Math.max(maxOddFreq, freq[charIdx]);
                            hasOdd = true;
                        } else { // non-zero and even
                            minEvenFreq = Math.min(minEvenFreq, freq[charIdx]);
                            hasEven = true;
                        }
                    }
                }

                if (hasOdd && hasEven) {
                    maxDifference = Math.max(maxDifference, maxOddFreq - minEvenFreq);
                    found = true;
                }
            }
        }
        // The problem guarantees a solution exists, but for robustness:
        return found ? maxDifference : 0; 
    }
}
```
### Algorithm
- Use three nested loops to generate all substrings and calculate their character frequencies.
- The outer loop `i` iterates from `0` to `n-1` for the start of the substring.
- The second loop `j` iterates from `i` to `n-1` for the end of the substring.
- Check if the substring length `j - i + 1` is at least `k`.
- If the length is valid, a third loop `l` from `i` to `j` calculates the frequency of each character ('0' through '4') in the substring `s[i...j]`.
- After calculating frequencies, iterate through all possible pairs of characters `(a, b)`.
- If `freq[a]` is odd and `freq[b]` is non-zero and even, calculate the difference `freq[a] - freq[b]`.
- Keep track of the maximum difference found across all valid substrings and character pairs.

## Optimized Brute Force
This approach improves upon the naive brute-force method by optimizing the frequency calculation. Instead of re-calculating frequencies for each substring from scratch, it maintains a running count of character frequencies as the substring's endpoint expands.
**Time:** O(N²). Two nested loops run, and the work inside the inner loop is constant time (since the alphabet size is constant). For N up to 3 * 10⁴, N² is too large. · **Space:** O(1), as the frequency map size is constant.
**Pros:** More efficient than the naive O(N³) approach.; Still relatively simple to implement.
**Cons:** Still too slow for the given constraints, leading to a 'Time Limit Exceeded' error.
### Explanation
We iterate through all possible starting positions `i` of a substring. For each `i`, we start building a substring by iterating a second pointer `j` from `i` to the end of the string. We use a frequency array to keep track of character counts for the substring `s[i...j]`. When we move from `j` to `j+1`, we simply increment the count for `s.charAt(j+1)`. This avoids the third loop for frequency calculation, reducing the work done for each substring. After updating the frequencies for `s[i...j]`, if its length is at least `k`, we check the conditions for all character pairs and update the maximum difference accordingly.

```java
class Solution {
    public int maxDiff(String s, int k) {
        int n = s.length();
        int maxDifference = Integer.MIN_VALUE;
        boolean found = false;

        for (int i = 0; i < n; i++) {
            int[] freq = new int[5];
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - '0']++;
                if (j - i + 1 < k) {
                    continue;
                }

                int maxOddFreq = -1;
                int minEvenFreq = Integer.MAX_VALUE;
                boolean hasOdd = false;
                boolean hasEven = false;

                for (int charIdx = 0; charIdx < 5; charIdx++) {
                    if (freq[charIdx] > 0) {
                        if (freq[charIdx] % 2 != 0) {
                            maxOddFreq = Math.max(maxOddFreq, freq[charIdx]);
                            hasOdd = true;
                        } else { // non-zero and even
                            minEvenFreq = Math.min(minEvenFreq, freq[charIdx]);
                            hasEven = true;
                        }
                    }
                }

                if (hasOdd && hasEven) {
                    maxDifference = Math.max(maxDifference, maxOddFreq - minEvenFreq);
                    found = true;
                }
            }
        }
        return found ? maxDifference : 0;
    }
}
```
### Algorithm
- Use two nested loops. The outer loop `i` fixes the start of the substring.
- The inner loop `j` extends the end of the substring from `i` to `n-1`.
- For a fixed `i`, maintain a frequency map for the current substring `s[i...j]`.
- As `j` increments, update the frequency map in O(1) time by just incrementing the count for the new character `s[j]`.
- For each substring `s[i...j]` of length at least `k`, iterate through all pairs of characters `(a, b)`.
- Check if `freq[a]` is odd and `freq[b]` is non-zero and even.
- If the conditions are met, update the global maximum difference with `freq[a] - freq[b]`.

## Sliding Window with Prefix Parities
This efficient approach reformulates the problem using prefix sums and focuses on optimizing the search for the best substring for each fixed pair of characters `(a, b)`. By using a sliding window-like mechanism combined with state tracking based on count parities, it achieves a linear time complexity.
**Time:** O(N * C²), where N is the string length and C is the alphabet size. We iterate through all C*(C-1) pairs of characters, and for each pair, we perform a single O(N) pass. Since C is a small constant (5), the complexity is effectively linear, O(N). · **Space:** O(N * C), where N is the string length and C is the alphabet size (5). This is for storing the prefix sums. The state tables (`min1`, `min2`) take constant space O(1) for each pair of (a, b).
**Pros:** Highly efficient with linear time complexity.; Guaranteed to pass within time limits for the given constraints.
**Cons:** More complex to implement due to the state management with two minimums and parity conditions.
### Explanation
For every distinct pair of characters `(a, b)`, we aim to find the maximum value of `freq(a) - freq(b)`. We can express the frequency of a character in a substring `s[i..j]` using prefix sums: `freq(c, i, j) = prefix_sum[c][j] - prefix_sum[c][i-1]`. The expression to maximize becomes `(count[a][j] - count[b][j]) - (count[a][i-1] - count[b][i-1])`.

We can iterate through all possible end points `j` and for each `j`, find the best start point `i` (or `p = i-1`). The best `p` is one that minimizes `count[a][p] - count[b][p]` while satisfying the problem's constraints. The constraints on `freq(a)` and `freq(b)` translate to parity conditions on the prefix sums at indices `j` and `p`.

To efficiently find the best `p` for each `j`, we maintain tables that store the minimum values of `count[a][p] - count[b][p]` seen so far, categorized by the parity of `count[a][p]` and `count[b][p]`. The tricky part is the `freq(b) != 0` constraint, which means `count[b][p] != count[b][j]`. To handle this, we don't just store the minimum value for each parity state, but the two smallest distinct values. If the best minimum corresponds to a `p` where `count[b][p] == count[b][j]`, we can fall back to the second minimum, ensuring the non-zero constraint is met.

```java
class Solution {
    // Helper class to store value and corresponding count of character 'b'
    static class Info {
        int value;
        int countB;

        Info(int value, int countB) {
            this.value = value;
            this.countB = countB;
        }
    }

    public int maxDiff(String s, int k) {
        int n = s.length();
        int[][] prefixCounts = new int[5][n + 1];
        for (int i = 0; i < n; i++) {
            for (int c = 0; c < 5; c++) {
                prefixCounts[c][i + 1] = prefixCounts[c][i];
            }
            prefixCounts[s.charAt(i) - '0'][i + 1]++;
        }

        int maxDifference = Integer.MIN_VALUE;

        for (int a = 0; a < 5; a++) {
            for (int b = 0; b < 5; b++) {
                if (a == b) continue;

                Info[][] min1 = new Info[2][2];
                Info[][] min2 = new Info[2][2];
                for(int i=0; i<2; i++) for(int j=0; j<2; j++) {
                    min1[i][j] = new Info(Integer.MAX_VALUE, -1);
                    min2[i][j] = new Info(Integer.MAX_VALUE, -1);
                }

                // Base case for empty prefix (p = -1)
                min1[0][0] = new Info(0, 0);

                for (int j = 0; j < n; j++) {
                    int p = j - k + 1;
                    if (p >= 0) { // Corresponds to prefix ending at p-1
                        int pa_p = prefixCounts[a][p] % 2;
                        int pb_p = prefixCounts[b][p] % 2;
                        int val_p = prefixCounts[a][p] - prefixCounts[b][p];
                        int cb_p = prefixCounts[b][p];

                        // Update min1 and min2 tables
                        if (val_p < min1[pa_p][pb_p].value) {
                            min2[pa_p][pb_p] = min1[pa_p][pb_p];
                            min1[pa_p][pb_p] = new Info(val_p, cb_p);
                        } else if (val_p > min1[pa_p][pb_p].value && val_p < min2[pa_p][pb_p].value) {
                            min2[pa_p][pb_p] = new Info(val_p, cb_p);
                        }
                    }

                    if (j >= k - 1) {
                        int pa_j = prefixCounts[a][j + 1] % 2;
                        int pb_j = prefixCounts[b][j + 1] % 2;
                        int val_j = prefixCounts[a][j + 1] - prefixCounts[b][j + 1];
                        int cb_j = prefixCounts[b][j + 1];

                        int target_pa = (1 - pa_j + 2) % 2;
                        int target_pb = pb_j;

                        Info bestP = min1[target_pa][target_pb];
                        if (bestP.value != Integer.MAX_VALUE) {
                            if (bestP.countB != cb_j) {
                                maxDifference = Math.max(maxDifference, val_j - bestP.value);
                            } else {
                                Info secondBestP = min2[target_pa][target_pb];
                                if (secondBestP.value != Integer.MAX_VALUE) {
                                    maxDifference = Math.max(maxDifference, val_j - secondBestP.value);
                                }
                            }
                        }
                    }
                }
            }
        }
        return maxDifference;
    }
}
```
### Algorithm
- The main idea is to fix the characters `a` and `b` and then find the optimal substring in O(N) time. This process is repeated for all `5 * 4 = 20` pairs of `(a, b)`.
- Precompute prefix sums `count[c][i]` for each character `c` up to index `i`.
- The difference `freq(a) - freq(b)` for a substring `s[p+1...j]` can be written as `(count[a][j] - count[b][j]) - (count[a][p] - count[b][p])`.
- We iterate `j` from `0` to `n-1`. For each `j`, we need to find an index `p <= j-k` that minimizes `count[a][p] - count[b][p]` subject to parity constraints.
- The parity constraints are: `freq(a)` is odd, meaning `count[a][j]` and `count[a][p]` have different parities. `freq(b)` is even, meaning `count[b][j]` and `count[b][p]` have the same parity.
- The non-zero constraint for `freq(b)` means `count[b][j] != count[b][p]`.
- To handle this, we maintain two tables, `min1` and `min2`, for each of the four parity combinations of `(count[a][p], count[b][p])`. These tables store the two smallest values of `count[a][p] - count[b][p]` and the corresponding `count[b][p]` value.
- As we iterate `j`, we update these tables with information from prefix `p = j-k`.
- For the current `j`, we determine the required parities for `p`. We query our tables for the best `p`. If the best `p` (from `min1`) violates the non-zero constraint (i.e., `count[b][p] == count[b][j]`), we use the second-best `p` (from `min2`).
- The overall maximum difference is updated in each step.

# Solutions
### Java

```java
class 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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```