LeetCode 题解工作台
奇偶频次间的最大差值 II
给你一个字符串 s 和一个整数 k 。 请你找出 s 的子字符串 subs 中两个字符的出现频次之间的 最大 差值， freq[a] - freq[b] ，其中： subs 的长度 至少 为 k 。 字符 a 在 subs 中出现奇数次。 字符 b 在 subs 中出现非 0 偶数次。 Create…
4
题型
6
代码语言
3
相关题
当前训练重点
困难 · 滑动窗口（状态滚动更新）
答案摘要
我们希望从字符串 中找出一个子字符串 ，满足以下条件： - 子字符串 的长度至少为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你一个字符串 s 和一个整数 k 。请你找出 s 的子字符串 subs 中两个字符的出现频次之间的 最大 差值，freq[a] - freq[b] ，其中：
subs的长度 至少 为k。- 字符
a在subs中出现奇数次。 - 字符
b在subs中出现非 0 偶数次。
返回 最大 差值。
注意 ，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 * 104s仅由数字'0'到'4'组成。- 输入保证至少存在一个子字符串是由一个出现奇数次的字符和一个出现偶数次的字符组成。
1 <= k <= s.length
解题思路
方法一：枚举字符对 + 滑动窗口 + 前缀状态压缩
我们希望从字符串 中找出一个子字符串 ，满足以下条件：
- 子字符串 的长度至少为 。
- 子字符串 中字符 的出现次数为奇数。
- 子字符串 中字符 的出现次数为偶数。
- 最大化频次差值 ，其中 和 分别是字符 和 在 中的出现次数。
字符串 中的字符来自 '0' 到 '4'，共有 5 种字符。我们可以枚举所有不同字符对 ，总共最多 种组合。我们约定：
- 字符 是目标奇数频次的字符。
- 字符 是目标偶数频次的字符。
我们使用滑动窗口维护子串的左右边界，通过变量：
- 其中 表示左边界的前一个位置，窗口为 ；
- 为右边界，遍历整个字符串；
- 变量 和 分别表示当前窗口中字符 和 的出现次数；
- 变量 和 表示左边界 前的字符 和 的累计出现次数。
我们用一个二维数组 记录此前窗口左端可能的奇偶状态组合下的最小差值 ，其中 表示 且 时的最小 。
每次右移 后，如果窗口长度满足 且 ，我们尝试右移左边界 来收缩窗口，并更新对应的 。
此后，我们尝试更新答案：
这样，我们就能在每次右移 时计算出当前窗口的最大频次差值。
时间复杂度 ，其中 为字符串 的长度，而 为字符集大小（本题为 5）。空间复杂度 。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * |Σ|^2) since we consider all pairs of characters and slide the window over n elements. Space complexity is O(1) because only counts for two characters are maintained, independent of input size. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Expect candidates to fix two characters to reduce the problem scope.
- question_mark
Look for efficient sliding window implementation rather than recomputation per substring.
- question_mark
Check understanding of even vs odd frequency tracking within a running window.
常见陷阱
外企场景- error
Forgetting that substrings can contain more than two characters while only comparing the selected pair.
- error
Recomputing frequencies from scratch on every window, causing timeouts.
- error
Incorrectly handling even and odd frequency checks when frequencies are zero.
进阶变体
外企场景- arrow_right_alt
Compute maximum difference where substrings must contain exactly two distinct characters.
- arrow_right_alt
Find maximum difference considering all characters, not fixing pairs in advance.
- arrow_right_alt
Adjust the problem for strings with larger digit ranges, e.g., '0'-'9'.