这是 LeetCode 3445. 奇偶频次间的最大差值 II 的 Rust 实现。

解题思路

核心观察：字符串 `s` 仅由 `'0'``'4'` 组成，因此最多只有 5 种字符。可以暴力枚举所有字符对 `(a, b)`（`a` 为奇数频次，`b` 为偶数频次且非零），共 `5×4=20` 种组合。

问题转化：对于固定的 `(a, b)`，把 `a` 视为 `+1`，`b` 视为 `-1`，其余视为 `0`。问题转化为找一个长度至少为 `k` 的子数组，使得：
- `+1` 出现 奇数 次
- `-1` 出现 非零偶数 次
- 最大化子数组和（即 `freq[a] - freq[b]`）

滑动窗口 + 前缀状态压缩：
- 用前缀和记录 `a` 和 `b` 的累计出现次数
- 状态 `state = (cnt_a % 2) << 1 | (cnt_b % 2)`，只有 4 种状态
- 维护每种状态下最小的 `pre_a - pre_b`，使得后续查询时可以最大化 `(cur_a - cur_b) - (pre_a - pre_b)`
- 收缩左边界时确保子串中 `b` 至少出现 2 次（`cur_b - pre_b >= 2`），从而保证非零偶数

Rust 代码

```rust
impl Solution {
    pub fn max_difference(s: String, k: i32) -> i32 {
        let n = s.len();
        let s_bytes = s.as_bytes();
        let mut ans = i32::MIN;
        let k = k as i32;

        // 枚举奇数频次字符 a 和偶数频次字符 b（a ≠ b）
        // s 仅由 '0'~'4' 组成，最多 5×4=20 种组合
        for a in b'0'..=b'4' {
            for b in b'0'..=b'4' {
                if a == b {
                    continue;
                }

                // best[state] 记录状态 state 下最小的 (pre_a - pre_b)
                // state = (pre_a % 2) << 1 | (pre_b % 2)，取值 0~3
                let mut best = [i32::MAX; 4];

                let mut cur_a = 0i32; // 前缀 [0..r] 中 a 的个数
                let mut cur_b = 0i32; // 前缀 [0..r] 中 b 的个数
                let mut pre_a = 0i32; // 前缀 [0..l] 中 a 的个数
                let mut pre_b = 0i32; // 前缀 [0..l] 中 b 的个数
                let mut l = -1i32;    // 左边界在 a、b 计数数组中的索引（前缀长度）

                for r in 0..n {
                    let c = s_bytes[r];
                    if c == a {
                        cur_a += 1;
                    } else if c == b {
                        cur_b += 1;
                    }

                    // 收缩左边界，同时记录合法左端点的最小前缀差
                    // 条件：
                    // 1. 子串长度 >= k：r - l >= k
                    // 2. 子串中 b 至少出现 2 次（保证非零偶数）：cur_b - pre_b >= 2
                    // 3. 子串中 a 至少出现 1 次（配合奇偶性即为奇数）：cur_a - pre_a >= 1
                    while (r as i32 - l) >= k && (cur_b - pre_b) >= 2 && (cur_a - pre_a) >= 1 {
                        let state = (((pre_a & 1) << 1) | (pre_b & 1)) as usize;
                        best[state] = best[state].min(pre_a - pre_b);
                        l += 1;
                        let lc = s_bytes[l as usize];
                        if lc == a {
                            pre_a += 1;
                        } else if lc == b {
                            pre_b += 1;
                        }
                    }

                    // 查询：需要子串中 a 为奇数、 b 为偶数
                    // 即 pre_a % 2 != cur_a % 2，pre_b % 2 == cur_b % 2
                    let need_state = ((((cur_a & 1) ^ 1) << 1) | (cur_b & 1)) as usize;
                    if best[need_state] != i32::MAX {
                        ans = ans.max(cur_a - cur_b - best[need_state]);
                    }
                }
            }
        }

        ans
    }
}
```

复杂度分析

- 时间复杂度：`O(20 × n) = O(n)`，其中 `n = s.len()`。20 是字符对的枚举数，每种组合内是线性滑动窗口。
- 空间复杂度：`O(1)`，只使用了常数个变量和长度为 4 的 `best` 数组。

下载链接

[LeetCode 3445 Rust 实现](sandbox:///mnt/agents/output/leetcode_3445.rs)