点击获取AI摘要

3445. 奇偶频次间的最大差值 II H

给你一个字符串 s 和一个整数 k 。请你找出 s 的子字符串 subs 中两个字符的出现频次之间的最大差值，freq[a] - freq[b] ，其中：

subs 的长度至少为 k 。
字符 a 在 subs 中出现奇数次。
字符 b 在 subs 中出现偶数次。

返回最大差值。

注意，subs 可以包含超过 2 个 互不相同 的字符。.

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入： s = “12233”, k = 4

输出： -1

解释：

对于子字符串 "12233" ，'1' 的出现次数是 1 ，'3' 的出现次数是 2 。差值是 1 - 2 = -1 。

示例 2：

输入： s = “1122211”, k = 3

输出： 1

解释：

对于子字符串 "11222" ，'2' 的出现次数是 3 ，'1' 的出现次数是 2 。差值是 3 - 2 = 1 。

示例 3：

输入： s = “110”, k = 3

输出： -1

提示：

3 <= s.length <= 3 * 10⁴
s 仅由数字 '0' 到 '4' 组成。
输入保证至少存在一个子字符串是由一个出现奇数次的字符和一个出现偶数次的字符组成。
1 <= k <= s.length

问题分析

给定长度为 $n$ 的字符串 $s$ （字符集 $\{'0','1','2','3','4'\}$ ）和整数 $k$ ，需要在所有长度至少为 $k$ 的子串中，找到满足：

字符 $a$ 在子串内出现奇数次；
字符 $b$ 在子串内出现偶数次且至少出现一次；
最大化 $\mathrm{freq}(a)-\mathrm{freq}(b)$ 。

直接枚举所有子串显然会达到 $O(n^2)$ 或更高。需结合“枚举字符对 + 前缀差分 + 增量维护”将复杂度降至 $O(n)$ 。

算法思路

整体预处理
- 计算前缀计数矩阵
  $P[c][i]=\#\{\,s[0..i-1]\text{ 中字符 }c\}$
  对所有 $c\in\{0,\dots,4\}$ ， $i=0..n$ ，耗时 $O(5n)$ ；
- 同时记录每个字符 $c$ 的所有出现位置列表 $\mathrm{pos}[c]$ 。
枚举字符对 $(a,b)$
共 20 对，常数级：
- 构造长度为 $n+1$ 的差分数组
  $D[i]=P[a][i]-P[b][i],$
  和状态数组
  $S[i]=\bigl(P[a][i]\bmod2,\;P[b][i]\bmod2\bigr).$
- 准备字典 minD，存 4 种 $(p_a,p_b)$ 状态下已纳入前缀的最小 $D$ ，初始为 $+\infty$ 。
- 使用指针 j_ptr 初始为 $-1$ ，表示“已纳入”的最大前缀下标。
线性扫描
对每对 $(a,b)$ ，遍历 $i$ 从 $k$ 到 $n$ ：
- 计算此时合法起点上限
  
  $t=P[b][i],\quad \text{若 }t\ge1,\;j_{\max}=\min\bigl(i-k,\;\mathrm{pos}[b][t-1]\bigr)\text{；否则 }j_{\max}=-1.$
- 增量纳入：
  1
  2
  3
  4
  while j_ptr < j_max:
  j_ptr += 1
  st = S[j_ptr]
  minD[st] = min(minD[st], D[j_ptr])
- 令当前终点状态为 $S[i]=(s_a,s_b)$ ，目标状态需 $a$ 奇、 $b$ 偶：
  
  $\mathrm{target}=(s_a \oplus 1,\;s_b).$
  
  若 \minD[\mathrm{target}]\neq+\infty，更新答案
  
  $\mathrm{ans}=\max\bigl(\mathrm{ans},\;D[i]-\min D[\mathrm{target}]\bigr).$

时间复杂度

前缀和位置列表预处理： $O(5n + n)=O(n)$
枚举 20 对 $(a,b)$ ，每对线性扫描 $O(n)$
总计： $\displaystyle O(n)$

代码分解

预处理
- 构造 P 和 pos；
主循环
- 枚举 a,b；
- 构造 D、S；
- 初始化 minD,j_ptr；
- 遍历 i=k..n 做“增量纳入”与“候选更新”；
返回结果
- 若未更新，返回 $-1$ ，否则返回 ans。

代码实现

class Solution:
    def maxDifference(self, s: str, k: int) -> int:
        n = len(s)
        idx = lambda c: ord(c) - ord('0')

        # 1) 预处理前缀计数 P 和位置列表 pos
        P = [[0] * (n + 1) for _ in range(5)]
        pos = [[] for _ in range(5)]
        for i, ch in enumerate(s):
            ci = idx(ch)
            pos[ci].append(i)
            for c in range(5):
                P[c][i + 1] = P[c][i]
            P[ci][i + 1] += 1

        ans = float('-inf')

        # 2) 枚举字符对 (a,b)
        for a in range(5):
            for b in range(5):
                if a == b:
                    continue

                # 构造差分 D 和状态 S
                D = [P[a][i] - P[b][i] for i in range(n + 1)]
                S = [(P[a][i] & 1, P[b][i] & 1) for i in range(n + 1)]

                # 初始化 4 状态的最小差分 +∞
                minD = {
                    (0, 0): float('inf'),
                    (0, 1): float('inf'),
                    (1, 0): float('inf'),
                    (1, 1): float('inf'),
                }
                j_ptr = -1

                # 3) 线性扫描 i=k..n
                for i in range(k, n + 1):
                    t = P[b][i]
                    if t >= 1:
                        j_max = min(i - k, pos[b][t - 1])
                    else:
                        j_max = -1

                    # 增量纳入前缀 j
                    while j_ptr < j_max:
                        j_ptr += 1
                        st_j = S[j_ptr]
                        minD[st_j] = min(minD[st_j], D[j_ptr])

                    # 更新答案
                    st_i = S[i]
                    target = (st_i[0] ^ 1, st_i[1])  # a 奇, b 偶
                    best = minD[target]
                    if best != float('inf'):
                        ans = max(ans, D[i] - best)

        return ans if ans != float('-inf') else -1