2025-08-14：奇偶频次间的最大差值Ⅱ。用go语言，给你一个字符串 s 和一个整数 k。请从 s 中选取任意一个长度不少于

福大大架构师每日一题

发布于 2025-08-14 09:19:06

19400

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-08-14：奇偶频次间的最大差值Ⅱ。用go语言，给你一个字符串 s 和一个整数 k。请从 s 中选取任意一个长度不少于 k 的连续片段（即子串），满足存在两个字符 a、b 使得：

• 在该子串中，字符 a 的出现次数为奇数；
• 字符 b 的出现次数为正且为偶数。

在所有满足条件的子串及字符对中，求出频次之差 freq[a] - freq[b] 的最大可能值，并返回该值。

说明：子串可以包含超过两个不同的字符。

3 <= s.length <= 3 * 10000。

s 仅由数字 '0' 到 '4' 组成。

输入保证至少存在一个子字符串是由一个出现奇数次的字符和一个出现偶数次的字符组成。

1 <= k <= s.length。

输入：s = "1122211", k = 3。

输出：1。

解释：

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

题目来自力扣3445。

分步描述过程：

1. 初始化变量：
- • 遍历所有可能的字符对 (a, b)，其中 a 和 b 是 '0' 到 '4' 的字符，且 a != b。
- • 对于每一对 (a, b)，初始化一个长度为 4 的数组 best，用于记录不同状态下的最小 (cntA - cntB) 值。初始时，best 的所有元素设为 math.MaxInt32。
- • 初始化滑动窗口的左右指针 left和right，以及计数器cntA和cntB（分别统计当前窗口中a和b的出现次数），以及prevA和prevB（记录滑动窗口左边界移动前的cntA和cntB）。
2. 滑动窗口遍历：
- • 使用右指针 right 遍历字符串 s，每次移动右指针时：
  - • 如果当前字符是 a，则 cntA++；如果是 b，则 cntB++。
- • 维护滑动窗口的左指针 left：
  - • 当窗口长度 (right - left) >= k 且 (cntB - prevB) >= 2 时，移动左指针 left：
    - • 计算左指针移动前的状态 leftStatus（由 prevA 和 prevB 的奇偶性决定）。
    - • 更新 best[leftStatus] 为 min(best[leftStatus], prevA - prevB)。
    - • 移动左指针 left，并更新 prevA 和 prevB（如果 s[left] 是 a 或 b）。
- • 计算当前右指针的状态 rightStatus（由 cntA 和 cntB 的奇偶性决定）。
- • 检查 best[rightStatus ^ 0b10] 是否有效（即不为 math.MaxInt32）：
  - • 如果有效，计算当前差值 (cntA - cntB) - best[rightStatus ^ 0b10]，并更新全局最大值 ans。
3. 状态定义：
- • 状态 status 是一个 2 位二进制数，高位表示 cntA 的奇偶性（奇数则为 1，偶数则为 0），低位表示 cntB 的奇偶性。
- • 状态的可能值为 0b00、0b01、0b10、0b11，分别对应 (cntA偶, cntB偶)、(cntA偶, cntB奇)、(cntA奇, cntB偶)、(cntA奇, cntB奇)。
- • rightStatus ^ 0b10 的作用是翻转 cntA 的奇偶性，确保 a 的出现次数为奇数，b 的出现次数为偶数。
4. 结果更新：
- • 对于每一对 (a, b)，通过滑动窗口和状态维护，计算可能的差值 (cntA - cntB) 的最大值。
- • 最终返回所有字符对和子串中的最大差值 ans。

时间复杂度和空间复杂度：

• 时间复杂度：
- • 外层循环遍历所有字符对 (a, b)，共有 5 * 4 = 20 种可能（因为 a != b）。
- • 内层滑动窗口遍历字符串 s，每次遍历的时间复杂度为 O(n)。
- • 因此，总时间复杂度为 O(20 * n) = O(n)。
• 空间复杂度：
- • 使用了固定大小的数组 best（长度为 4），以及常数个变量。
- • 因此，总空间复杂度为 O(1)。

总结：

该算法通过滑动窗口和状态压缩技术，高效地遍历所有可能的字符对和子串，确保在 O(n) 时间内解决问题，同时仅使用常数空间。

Go完整代码如下：

package main

import (
    "fmt"
    "math"
)

func maxDifference(s string, k int)int {
    n := len(s)
    ans := math.MinInt32
    for _, a := range []byte{'0', '1', '2', '3', '4'} {
        for _, b := range []byte{'0', '1', '2', '3', '4'} {
            if a == b {
                continue
            }
            best := make([]int, 4)
            for i := range best {
                best[i] = math.MaxInt32
            }
            cntA, cntB := 0, 0
            prevA, prevB := 0, 0
            left := -1
            for right := 0; right < n; right++ {
                if s[right] == a {
                    cntA++
                }
                if s[right] == b {
                    cntB++
                }
                for right-left >= k && cntB-prevB >= 2 {
                    leftStatus := getStatus(prevA, prevB)
                    if prevA-prevB < best[leftStatus] {
                        best[leftStatus] = prevA - prevB
                    }
                    left++
                    if s[left] == a {
                        prevA++
                    }
                    if s[left] == b {
                        prevB++
                    }
                }
                rightStatus := getStatus(cntA, cntB)
                if best[rightStatus^0b10] != math.MaxInt32 {
                    current := (cntA - cntB) - best[rightStatus^0b10]
                    if current > ans {
                        ans = current
                    }
                }
            }
        }
    }
    return ans
}

func getStatus(cntA, cntB int)int {
    return ((cntA & 1) << 1) | (cntB & 1)
}

func main() {
    s := "1122211"
    k := 3
    result := maxDifference(s, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math

defmax_difference(s: str, k: int) -> int:
    n = len(s)
    ans = -math.inf
    for a in ['0', '1', '2', '3', '4']:
        for b in ['0', '1', '2', '3', '4']:
            if a == b:
                continue
            best = [math.inf] * 4
            cnt_a, cnt_b = 0, 0
            prev_a, prev_b = 0, 0
            left = -1
            for right inrange(n):
                if s[right] == a:
                    cnt_a += 1
                if s[right] == b:
                    cnt_b += 1
                while right - left >= k and cnt_b - prev_b >= 2:
                    left_status = get_status(prev_a, prev_b)
                    if prev_a - prev_b < best[left_status]:
                        best[left_status] = prev_a - prev_b
                    left += 1
                    if s[left] == a:
                        prev_a += 1
                    if s[left] == b:
                        prev_b += 1
                right_status = get_status(cnt_a, cnt_b)
                if best[right_status ^ 0b10] != math.inf:
                    current = (cnt_a - cnt_b) - best[right_status ^ 0b10]
                    if current > ans:
                        ans = current
    return ans

defget_status(cnt_a: int, cnt_b: int) -> int:
    return ((cnt_a & 1) << 1) | (cnt_b & 1)

if __name__ == "__main__":
    s = "1122211"
    k = 3
    result = max_difference(s, k)
    print(result)