1542.找出最长的超赞子字符串

【LetMeFly】1542.找出最长的超赞子字符串:前缀异或和(位运算)

力扣题目链接:https://leetcode.cn/problems/find-longest-awesome-substring/

给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。

「超赞子字符串」需满足满足下述两个条件:

  • 该字符串是 s 的一个非空子字符串
  • 进行任意次数的字符交换后,该字符串可以变成一个回文字符串

 

示例 1:

输入:s = "3242415"
输出:5
解释:"24241" 是最长的超赞子字符串,交换其中的字符后,可以得到回文 "24142"
TEXT

示例 2:

输入:s = "12345678"
输出:1
TEXT

示例 3:

输入:s = "213123"
输出:6
解释:"213123" 是最长的超赞子字符串,交换其中的字符后,可以得到回文 "231132"
TEXT

示例 4:

输入:s = "00"
输出:2
TEXT

 

提示:

  • 1 <= s.length <= 10^5
  • s 仅由数字组成

解题方法:前缀和+哈希表+位运算

回文串有两种情况:

  1. 所有字符都出现了偶数次、
  2. 有且仅有一个字符出现了奇数次。

也就是说我们只用关心每个字符出现次数是奇数还是偶数即可。因此我们可以使用一个数maskmask的第i位表示数字i出现次数是否为奇数次。

加入在mask的基础上又出现了i,则新的mask的计算公式为:mask ^= 1 << i

我们只需要遍历一遍字符串,并且使用哈希表,哈希表ma[mask]为前面所有数字结果为mask的第一次出现位置。则遍历过程中有“

  • 若当前mask出现过,则这两次出现位置之间所有字符都出现了偶数次,满足回文串要求;
  • 若当前mask变化一位后在哈希表中存在,则这两次出现位置之间的字符串只有一个出现了奇数次,满足回文串要求。

遍历结束,算法结束。

  • 时间复杂度O(len(s)×C),其中C是字符个数,这里C=10
  • 空间复杂度O(minlen(s),2C)

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
}
};
CPP

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def longestAwesome(self, s: str) -> int:
mask, ans = 0, 1
ma = {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] = i
for j in range(10):
mask2 = mask ^ (1 << j)
if mask2 in ma:
ans = max(ans, i - ma[mask2])
return ans
PYTHON

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

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


1542.找出最长的超赞子字符串
https://blog.letmefly.xyz/2024/05/20/LeetCode 1542.找出最长的超赞子字符串/
作者
发布于
2024年5月20日
许可协议