🔗 🔴 3445. Maximum Difference Between Even and Odd Frequency II

Problem Statement

題目簡述

給定一個僅由數字 '0' 到 '4' 組成的字串 $s$ 以及一個整數 $k$。

我們需要尋找一個長度至少為 $k$ 的子字串，使得其中某兩個不同字元 $a$ 與 $b$ 的出現次數差值 $\text{freq}[a] - \text{freq}[b]$ 最大，且滿足：

• 字元 $a$ 在該子字串中出現奇數次。
• 字元 $b$ 在該子字串中出現偶數次。

傳回這個最大的差值。

註：子字串中可以包含除了 $a$ 和 $b$ 以外的其他字元。

Constraints

約束條件

• $3 \le s.\text{length} \le 3 \times 10^4$
• $s$ 僅由字元 '0' 到 '4' 組成。
• 輸入保證至少存在一個合法的子字串，其中包含一個出現奇數次的字元與一個出現偶數次的字元。
• $1 \le k \le s.\text{length}$

---

思路：枚舉雙字元 + 前綴和 + 雙指標滑動窗口

本題是一道非常經典的 「枚舉右，維護左」 與 「前綴和轉化」 的綜合優化題。

1. 關鍵觀察：字元集極小

字串只包含 '0' 到 '4'，字元集大小 $|\Sigma| = 5$。因此可以直接枚舉有序字元對 $(a,b)$：

• $a$ 代表在子字串中出現奇數次的字元。
• $b$ 代表在子字串中出現偶數次的字元。
• 一共只有 $5 \times 4 = 20$ 種配對。

所以問題變成：對每一組 $(a,b)$，用 $\mathcal{O}(n)$ 求出合法子字串的最大差值。

---

2. 前綴和與公式變形

固定 $a$ 與 $b$ 後，目標是在一個長度至少為 $k$ 的區間 $[l,r]$ 中，最大化 $a$ 與 $b$ 的出現次數差。

定義前綴和陣列 $s_a$，其中 $s_a[i]$ 表示前綴 $s[0 \dots i-1]$ 中字元 $a$ 的出現次數。那麼：

$$sum_a(l, r) = s_a[r+1] - s_a[l]$$

同理，$b$ 的出現次數為 $sum_b(l, r) = s_b[r+1] - s_b[l]$。

我們希望最大化：

$$\begin{aligned} sum_a(l, r) - sum_b(l, r) &= \big(s_a[r+1] - s_a[l]\big) - \big(s_b[r+1] - s_b[l]\big) \\ &= \big(s_a[r+1] - s_b[r+1]\big) - \big(s_a[l] - s_b[l]\big) \end{aligned}$$

式子右半部只跟左端點有關。因此枚舉右端點 $r$（令 $i=r+1$）時，只要維護所有合法左端點 $l$（令 $j=l$）中的最小 $s_a[l]-s_b[l]$，就能更新答案。

---

3. 維護合法左端點

接下來的問題是：枚舉右端點 $i$ 時，哪些左端點 $j$ 可以拿來更新答案？

左端點需要滿足兩類「可加入」條件：

• 長度足夠：$i-j \ge k$。
• 區間內確實包含 $a$ 與 $b$：$s_a[j] < s_a[i]$ 且 $s_b[j] < s_b[i]$。

因此可以用左指標 left 往右掃，把已經滿足上述條件的左端點加入維護結構。加入時，根據 $s_a[\text{left}]$ 與 $s_b[\text{left}]$ 的奇偶性，把 $s_a[\text{left}]-s_b[\text{left}]$ 更新到對應狀態的最小值中。

奇偶狀態的二進位表示

左端點的 $s_a[j]$ 與 $s_b[j]$ 各有兩種奇偶性，可以壓成 $4$ 種狀態：

$$\text{state} = ((s_a[j] \bmod 2) \ll 1) \mid (s_b[j] \bmod 2)$$

用大小為 $4$ 的陣列 min_sl 記錄每種狀態下 $s_a[j]-s_b[j]$ 的最小值。

加入合法左端點後，還要根據當前右端點的奇偶性查詢正確狀態：

• $a$ 的出現次數 $s_a[i]-s_a[j]$ 必須為奇數，所以 $s_a[j]$ 與 $s_a[i]$ 奇偶性相反。
• $b$ 的出現次數 $s_b[i]-s_b[j]$ 必須為偶數，所以 $s_b[j]$ 與 $s_b[i]$ 奇偶性相同。

也就是查詢：

• $s_a[j] \equiv s_a[i] \oplus 1 \pmod 2$。
• $s_b[j] \equiv s_b[i] \pmod 2$。

從 min_sl 取出這個狀態的最小值，即可更新答案。

為什麼加入左端點時要檢查 $s_a[j] < s_a[i]$ 與 $s_b[j] < s_b[i]$？

只看長度會把「某個字元出現 $0$ 次」的區間也算進來。雖然 $0$ 是偶數，但題目要求選出的 $a$ 與 $b$ 都要在子字串中出現。

複雜度分析

• 時間複雜度：$\mathcal{O}(|\Sigma|^2 \cdot n)$。其中 $|\Sigma| = 5$ 為字元集大小，$n$ 為字串長度。
• 空間複雜度：$\mathcal{O}(n)$。

---

Code

class Solution:
    def maxDifference(self, s: str, k: int) -> int:
        n = len(s)
        nums = list(map(int, s))
        cnt = [0] * 5
        for x in nums:
            cnt[x] += 1

        ans = -inf
        for a in range(5):
            for b in range(5):
                if a == b or cnt[a] == 0 or cnt[b] == 0:
                    continue
                # min(sa[j] - sb[j])，且 (sa_j, sb_j) 的奇偶性分別為 (0, 0), (0, 1), (1, 0), (1, 1)
                min_sl = [inf] * 4
                sa = [0] * (n + 1)
                sb = [0] * (n + 1)
                left = 0
                for i, x in enumerate(nums, start=1):
                    sa[i] = sa[i - 1] + (x == a)
                    sb[i] = sb[i - 1] + (x == b)
                    while i - left >= k and sa[left] < sa[i] and sb[left] < sb[i]:
                        state = ((sa[left] & 1) << 1) | (sb[left] & 1)
                        min_sl[state] = min(min_sl[state], sa[left] - sb[left])
                        left += 1
                    # 因為 a 需要有奇數個，因此 sa[j] 的奇偶性需要與 sa[i] 相反
                    state = ((sa[i] & 1 ^ 1) << 1) | (sb[i] & 1)
                    ans = max(ans, sa[i] - sb[i] - min_sl[state])
        return ans  # 題目保證至少有一個合法的子字串