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

解题思路

字符串 `s` 仅由 `'0'``'4'` 组成，因此最多只有 5 种字符。核心思路是：

1. 枚举字符对：暴力枚举所有 `(a, b)` 组合（`a` 为奇数频次，`b` 为偶数频次且非零），共 `5×4=20` 种。
2. 前缀状态压缩：状态 `state = (cnt_a % 2) << 1 | (cnt_b % 2)`，只有 4 种可能。
3. 滑动窗口维护最小值：用双指针维护每种状态下最小的 `pre_a - pre_b`，使得后续查询时可以最大化 `(cur_a - cur_b) - (pre_a - pre_b)`。
4. 收缩条件：确保子串长度 `≥ k`，`b` 至少出现 2 次（非零偶数），`a` 至少出现 1 次（配合奇偶性即为奇数）。

JavaScript 代码

```javascript
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var maxDifference = function(s, k) {
    const n = s.length;
    let ans = -Infinity;
    
    // 预先将字符串转为 charCode 数组，避免重复调用 charCodeAt
    const sCodes = new Array(n);
    for (let i = 0; i < n; i++) {
        sCodes[i] = s.charCodeAt(i);
    }
    
    // 枚举 '0'(48) ~ '4'(52)
    for (let a = 48; a <= 52; a++) {
        for (let b = 48; b <= 52; b++) {
            if (a === b) continue;
            
            // best[state] 记录状态 state 下最小的 (preA - preB)
            // state = (preA % 2) << 1 | (preB % 2)，取值 0~3
            const best = [Infinity, Infinity, Infinity, Infinity];
            
            let curA = 0;  // 前缀 [0..r] 中 a 的个数
            let curB = 0;  // 前缀 [0..r] 中 b 的个数
            let preA = 0;  // 前缀 [0..l] 中 a 的个数
            let preB = 0;  // 前缀 [0..l] 中 b 的个数
            let l = -1;    // 左边界索引（前缀长度）
            
            for (let r = 0; r < n; r++) {
                const c = sCodes[r];
                if (c === a) {
                    curA++;
                } else if (c === b) {
                    curB++;
                }
                
                // 收缩左边界，同时记录合法左端点的最小前缀差
                // 条件：
                // 1. 子串长度 >= k：r - l >= k
                // 2. 子串中 b 至少出现 2 次（保证非零偶数）：curB - preB >= 2
                // 3. 子串中 a 至少出现 1 次（配合奇偶性即为奇数）：curA - preA >= 1
                while (r - l >= k && curB - preB >= 2 && curA - preA >= 1) {
                    const state = ((preA & 1) << 1) | (preB & 1);
                    best[state] = Math.min(best[state], preA - preB);
                    l++;
                    const lc = sCodes[l];
                    if (lc === a) {
                        preA++;
                    } else if (lc === b) {
                        preB++;
                    }
                }
                
                // 查询：需要子串中 a 为奇数、 b 为偶数
                // 即 preA % 2 != curA % 2，preB % 2 == curB % 2
                const needState = (((curA & 1) ^ 1) << 1) | (curB & 1);
                if (best[needState] !== Infinity) {
                    ans = Math.max(ans, curA - curB - best[needState]);
                }
            }
        }
    }
    
    return ans;
};
```

复杂度分析

- 时间复杂度：`O(20 × n) = O(n)`，其中 `n = s.length`。20 是字符对的枚举数，每种组合内是线性滑动窗口。
- 空间复杂度：`O(n)`，用于存储 `sCodes` 数组（也可优化至 `O(1)`，直接用 `s.charCodeAt(r)`）。

下载链接

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