Hard
题目描述
给你一个字符串 s 和一个整数 k。你的任务是找到子串 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^4s只包含数字 ‘0’ 到 ‘4’- 输入保证至少有一个子串包含频率为偶数的字符和频率为奇数的字符
1 <= k <= s.length
解题思路
这道题的核心思路是枚举所有可能的字符对，然后利用前缀和技术来高效计算子串中字符频率的奇偶性。
主要步骤：
枚举字符对：由于字符串只包含 ‘0’-‘4’，我们可以枚举所有字符对 (a, b)，其中 a 需要奇数频率，b 需要偶数频率。
奇偶性状态表示：对于每个字符对，我们维护一个状态，用二进制位表示两个字符频率的奇偶性。状态有四种：
- 00: 两个字符频率都是偶数
- 01: a偶数，b奇数
- 10: a奇数，b偶数（这是我们想要的状态）
- 11: 两个字符频率都是奇数
前缀和优化：对于每个位置，我们记录到达该位置时每种状态的最早出现位置。当我们到达位置 i 且状态为 10 时，我们需要找到之前状态为 00 的最早位置，这样可以保证子串长度最大化，从而最大化频率差。
计算最大差值：对于有效的子串，字符 a 的频率为奇数，字符 b 的频率为偶数，我们计算 freq[a] - freq[b] 的最大值。
时间复杂度：O(n)，其中 n 是字符串长度，因为字符种类是常数。
推荐解法：使用前缀和 + 状态压缩的方法，这是最优解法。
代码实现
class Solution {
public:
int maxDifference(string s, int k) {
int n = s.length();
int maxDiff = INT_MIN;
// 枚举所有字符对
for (char a = '0'; a <= '4'; a++) {
for (char b = '0'; b <= '4'; b++) {
if (a == b) continue;
// 状态：00, 01, 10, 11 (a的奇偶性, b的奇偶性)
vector<int> firstPos(4, -1);
firstPos[0] = 0; // 初始状态：都是偶数频率(0)
int countA = 0, countB = 0;
for (int i = 0; i < n; i++) {
if (s[i] == a) countA++;
if (s[i] == b) countB++;
int state = (countA % 2) * 2 + (countB % 2);
// 如果当前状态是10 (a奇数, b偶数)，且b频率>0
if (state == 2 && countB > 0) {
// 寻找之前状态为00的位置
if (firstPos[0] != -1 && i + 1 - firstPos[0] >= k) {
maxDiff = max(maxDiff, countA - countB);
}
}
// 更新状态的最早出现位置
if (firstPos[state] == -1) {
firstPos[state] = i + 1;
}
}
}
}
return maxDiff == INT_MIN ? -1 : maxDiff;
}
};
class Solution:
def maxDifference(self, s: str, k: int) -> int:
n = len(s)
max_diff = float('-inf')
# 枚举所有字符对
for a in '01234':
for b in '01234':
if a == b:
continue
# 状态：00, 01, 10, 11 (a的奇偶性, b的奇偶性)
first_pos = [-1] * 4
first_pos[0] = 0 # 初始状态：都是偶数频率(0)
count_a = count_b = 0
for i in range(n):
if s[i] == a:
count_a += 1
if s[i] == b:
count_b += 1
state = (count_a % 2) * 2 + (count_b % 2)
# 如果当前状态是10 (a奇数, b偶数)，且b频率>0
if state == 2 and count_b > 0:
# 寻找之前状态为00的位置
if first_pos[0] != -1 and i + 1 - first_pos[0] >= k:
max_diff = max(max_diff, count_a - count_b)
# 更新状态的最早出现位置
if first_pos[state] == -1:
first_pos[state] = i + 1
return max_diff if max_diff != float('-inf') else -1
public class Solution {
public int MaxDifference(string s, int k) {
int n = s.Length;
int maxDiff = int.MinValue;
// 枚举所有字符对
for (char a = '0'; a <= '4'; a++) {
for (char b = '0'; b <= '4'; b++) {
if (a == b) continue;
// 状态：00, 01, 10, 11 (a的奇偶性, b的奇偶性)
int[] firstPos = new int[4];
for (int j = 0; j < 4; j++) firstPos[j] = -1;
firstPos[0] = 0; // 初始状态：都是偶数频率(0)
int countA = 0, countB = 0;
for (int i = 0; i < n; i++) {
if (s[i] == a) countA++;
if (s[i] == b) countB++;
int state = (countA % 2) * 2 + (countB % 2);
// 如果当前状态是10 (a奇数, b偶数)，且b频率>0
if (state == 2 && countB > 0) {
// 寻找之前状态为00的位置
if (firstPos[0] != -1 && i + 1 - firstPos[0] >= k) {
maxDiff = Math.Max(maxDiff, countA - countB);
}
}
// 更新状态的最早出现位置
if (firstPos[state] == -1) {
firstPos[state] = i + 1;
}
}
}
}
return maxDiff == int.MinValue ? -1 : maxDiff;
}
}
var maxDifference = function(s, k) {
const n = s.length;
let maxDiff = -Infinity;
for (let i = 0; i <= n - k; i++) {
const freq = new Array(5).fill(0);
for (let j = i; j < n; j++) {
freq[s[j] - '0']++;
if (j - i + 1 >= k) {
let maxOdd = -Infinity;
let minEven = Infinity;
for (let c = 0; c < 5; c++) {
if (freq[c] % 2 === 1) {
maxOdd = Math.max(maxOdd, freq[c]);
} else if (freq[c] > 0) {
minEven = Math.min(minEven, freq[c]);
}
}
if (maxOdd !== -Infinity && minEven !== Infinity) {
maxDiff = Math.max(maxDiff, maxOdd - minEven);
}
}
}
}
return maxDiff;
};
复杂度分析
| 复杂度类型 | 值 |
|---|---|
| 时间复杂度 | O(n) |
| 空间复杂度 | O(1) |
注：虽然有双重循环枚举字符对，但由于字符只有5种(‘0’-‘4’)，所以是常数级别，总体时间复杂度为O(n)。