LeetCode 1542.找出最长的超赞子字符串：前缀异或和（位运算）

【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