🔗 🔴 1542. Find Longest Awesome Substring 2222

tags: `Biweekly Contest 32` `前綴和(Prefix Sum)` `前綴異或和` `位運算(Bit Manipulation)` `狀態壓縮` `雜湊表(Hash Table)`

題意

給定一個字串 $s$ ，一個 超棒子字串(awesome substring) 是 $s$ 的非空子字串，使得我們可以進行任意次數的交換來使其成為一個回文字符串。

返回 $s$ 中最長超棒子字串的長度。

思路：前綴異或和 + 狀態壓縮 + 雜湊表(Hash Table)

由於可以重新排列，因此我們只要關心子字串的長度是否為奇數，以及每個字元的出現次數的奇偶性即可。

若子字串長度為偶數，則所有字元的出現次數都應為偶數。
若子字串長度為奇數，則除了一個字元的出現次數為奇數外，其他字元的出現次數都應為偶數。

由於字串中的字元只包含了 $10$ 個數字，因此我們可以用一個狀態 $cur$ 來表示每個字元的出現次數的奇偶性，其中 $cur << i$ 為 $1$ 表示第 $i$ 個字元出現奇數次， $0$ 表示出現偶數次。
從字串的第一個字元開始，我們可以計算每個位置的前綴異或和 $cur$ ，若有兩個位置的前綴異或和相同，即 $cur_i = cur_j \Rightarrow cur_i \oplus cur_j = 0$ ，，則這兩個位置之間的子字串滿足條件。

對於情況 1，顯然每個狀態與先前出現過的相同狀態就構成了一個符合條件的子字串；
對於情況 2，若存在一個狀態與自己 XOR 後只有一個 1 的狀態，則兩者間的子字串就滿足條件，因此可以分別反轉當前狀態每一位，檢查是否存在這樣的狀態。

因此我們只需要一個雜湊表 $last$ 來保存每個狀態「最早」出現的位置，當再次出現時計算兩者間的距離即可。

由於空字串的狀態為所有字元出現次數都為偶數，即 $0$ ，位置可以視為 $-1$ ，因此初始化 $last = \{0: -1\}$ 。

複雜度分析

時間複雜度 $\mathcal{O}(n \Sigma)$ ，其中 $n$ 為字串長度， $\Sigma$ 為字元集大小，本題中 $\Sigma = 10$ 。
空間複雜度 $\mathcal{O}(\min(n, 2^D))$ 。

class Solution:
    def longestAwesome(self, s: str) -> int:
        last = {0: -1} # 保存每個狀態「最早」出現的位置
        ans, cur = 0, 0 # ans: 最長超棒子字串的長度, cur: 當前狀態(前綴異或和)
        for i, ch in enumerate(s):
            idx = ord(ch) - ord('0') # s 僅由數字組成
            cur ^= 1 << idx # 更新當前狀態
            if cur not in last:
                last[cur] = i # 這次迴圈不會用到這個狀態，所以可以直接更新
            else:
                ans = max(ans, i - last[cur])
            for j in range(10): # 檢查是否存在一個狀態與自己 XOR 後只有一個 1 的狀態
                if cur ^ (1 << j) in last:
                    ans = max(ans, i - last[cur ^ (1 << j)])
        return ans

class Solution {
public:
    int longestAwesome(string s) {
        unordered_map<int, int> mp;
        mp[0] = -1;
        int ans = 0, cur = 0;
        for (int i = 0; i < s.size(); i++) {
            cur ^= 1 << (s[i] - '0');
            if (mp.find(cur) == mp.end()) mp[cur] = i; // 這次迴圈不會用到這個狀態，所以可以直接更新
            else ans = max(ans, i - mp[cur]);
            for (int j = 0; j < 10; j++) { // 是否存在一個狀態與自己 XOR 後只有一個 1 的狀態
                int tmp = cur ^ (1 << j);
                if (mp.find(tmp) != mp.end()) ans = max(ans, i - mp[tmp]);
            }
        }
        return ans;
    }
};