【LetMeFly】1542.找出最長的超贊子字符串：前綴異或和（位運算）

力扣題目鏈接：https://leetcode.cn/problems/find-longest-awesome-substring/

給你一個字符串 s 。請返回 s 中最長的 超贊子字符串 的長度。

「超贊子字符串」需滿足滿足下述兩個條件：

• 該字符串是 s 的一個非空子字符串
• 進行任意次數的字符交換后，該字符串可以變成一個回文字符串

?

示例 1：

輸入：s = "3242415"
輸出：5
解釋："24241" 是最長的超贊子字符串，交換其中的字符后，可以得到回文 "24142"

示例 2：

輸入：s = "12345678"
輸出：1

示例 3：

輸入：s = "213123"
輸出：6
解釋："213123" 是最長的超贊子字符串，交換其中的字符后，可以得到回文 "231132"

示例 4：

輸入：s = "00"
輸出：2

?

提示：

• 1 <= s.length <= 10^5
• s 僅由數字組成

解題方法：前綴和+哈希表+位運算

回文串有兩種情況：

1. 所有字符都出現了偶數次、
2. 有且僅有一個字符出現了奇數次。

也就是說我們只用關心每個字符出現次數是奇數還是偶數即可。因此我們可以使用一個數$mask$，$mask$的第$i$位表示數字$i$出現次數是否為奇數次。

加入在$mask$的基礎上又出現了$i$，則新的$mask$的計算公式為：mask ^= 1 << i。

我們只需要遍歷一遍字符串，并且使用哈希表，哈希表$ma[mask]$為前面所有數字結果為$mask$的第一次出現位置。則遍歷過程中有“

• 若當前$mask$出現過，則這兩次出現位置之間所有字符都出現了偶數次，滿足回文串要求；
• 若當前$mask$變化一位后在哈希表中存在，則這兩次出現位置之間的字符串只有一個出現了奇數次，滿足回文串要求。

遍歷結束，算法結束。

• 時間復雜度$O(len(s)\times C)$，其中$C$是字符個數，這里$C=10$
• 空間復雜度 O ( min ? { l e n ( s ) , 2 C } ) O(\min\{len(s), 2^C\}) O(min{len(s),2C})

AC代碼

C++

class Solution {
public:int longestAwesome(string s) {int mask = 0, ans = 1;unordered_map<int, int> ma;ma[0] = -1;for (int i = 0; i < s.size(); i++) {mask ^= (1 << (s[i] - '0'));if (ma.count(mask)) {ans = max(ans, i - ma[mask]);}else {ma[mask] = i;}// 一個奇數次字符for (int j = 0; j < 10; j++) {int mask2 = mask ^ (1 << j);if (ma.count(mask2)) {ans = max(ans, i - ma[mask2]);}}}return ans;}
};

Python

class Solution:def longestAwesome(self, s: str) -> int:mask, ans = 0, 1ma = {0: -1}for i in range(len(s)):mask ^= 1 << (ord(s[i]) - ord('0'))if mask in ma:ans = max(ans, i - ma[mask])else:ma[mask] = ifor j in range(10):mask2 = mask ^ (1 << j)if mask2 in ma:ans = max(ans, i - ma[mask2])return ans

同步發文于CSDN和我的個人博客，原創不易，轉載經作者同意后請附上原文鏈接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/139077950