这是 LeetCode 3445. 奇偶频次间的最大差值 II（Maximum Difference Between Even and Odd Frequency II）的 Java 实现。

核心思路

枚举字符对 + 滑动窗口 + 前缀状态压缩

由于 `s` 仅由数字 `'0'` 到 `'4'` 组成，最多只有 5 种字符。枚举所有不同的字符对 (a, b)（a 为奇数频次，b 为偶数频次），共 5 \times 4 = 20 种组合。

对于每一对 (a, b)，使用滑动窗口维护子串：

- `curA`, `curB`：当前窗口 [l+1, r] 中 a 和 b 的出现次数
- `preA`, `preB`：左边界 l 之前 a 和 b 的累计出现次数
- `t[2][2]`：记录此前窗口左端可能的奇偶状态组合下的最小差值 `preA - preB`

状态压缩：用 `t[i][j]` 表示 `preA % 2 = i` 且 `preB % 2 = j` 时的最小 `preA - preB`。

滑动窗口收缩条件：
- 窗口长度 `r - l >= k`
- `curB - preB >= 2`（保证 b 在子串中出现至少 2 次，即非零偶数次）

更新答案：
\text{ans} = \max(\text{ans},\ \text{curA} - \text{curB} - t[(\text{curA} \bmod 2) \oplus 1][\text{curB} \bmod 2])

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;

        // 枚举所有字符对 (a, b)，a 为奇数频次，b 为偶数频次
        for (int a = 0; a < 5; ++a) {
            for (int b = 0; b < 5; ++b) {
                if (a == b) {
                    continue;
                }

                int curA = 0, curB = 0;  // 当前窗口 [l+1, r] 中 a 和 b 的出现次数
                int preA = 0, preB = 0;  // 左边界 l 之前 a 和 b 的累计出现次数
                // t[i][j]: preA%2=i, preB%2=j 时的最小 preA - preB
                int[][] t = {{inf, inf}, {inf, inf}};

                for (int l = -1, r = 0; r < n; ++r) {
                    // 右移 r，更新当前窗口计数
                    curA += s[r] == '0' + a ? 1 : 0;
                    curB += s[r] == '0' + b ? 1 : 0;

                    // 收缩左边界：保证窗口长度 >= k 且 b 出现至少 2 次
                    while (r - l >= k && curB - preB >= 2) {
                        // 更新 t：记录当前 preA, preB 状态的最小差值
                        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;
                    }

                    // 更新答案：需要 curA 为奇数，curB 为偶数
                    // 即 preA 的奇偶性要与 curA 相反，preB 的奇偶性要与 curB 相同
                    ans = Math.max(ans, curA - curB - t[curA & 1 ^ 1][curB & 1]);
                }
            }
        }

        return ans;
    }
}
```

复杂度分析

- 时间复杂度：O(n \times |\Sigma|^2)，其中 n 为字符串长度，|\Sigma| = 5 为字符集大小。枚举 20 种字符对，每种 O(n) 滑动窗口。
- 空间复杂度：O(1)，仅使用常数个变量和 2 \times 2 数组。