原题
给你一个字符串 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 仅由数字组成
思路 – 动态规划 & 状态压缩
分析回文串的特性：如果 S 是回文字符串，那么所有字符中，出现的次数为奇数的最多只有一种字符。如：
S = “1231233” // 只有一个字符 c 的出现次数为奇数
S = “123123” // 没有任何一个字符的出现次数为奇数
利用这个特性，通过状态压缩 —— 以二进制位表示字符串中字符出现的奇偶性。如：(1001)_2代表，字符 “0” 与 “3” 出现的次数为奇数，字符 “1” 与 “2” 出现的次数为偶数（或者没有出现过），处理字符串中所有前缀的状态。
每一个前缀字符串压缩成一个状态作为 Key，其 Value 为当前状态在字符串中出现的位置索引最小的一个值（利用其可以计算长度）。
当处理一个前缀字符串时，它的状态会有如下几种情况：
- 出现次数为奇数的字符小于等于 1 次，那么当前前缀字符串即可组成回文字符串
- 出现次数为奇数的字符大于 1 次
- 枚举任意一个字符，让其出现过的次数为奇数，通过前缀数组进行计算最大的长度
代码
class Solution {
public:
int longestAwesome(string s) {
int cnt[1 << 10];
memset(cnt, 0x3f, sizeof cnt);
int last = 0, ans = 0;
cnt[0] = -1;
for (int i = 0; i < s.size(); ++i) {
last ^= (1 << (s[i] - '0'));
int bcnt = 0;
for (int j = 0; j < 10; ++j) {
if ((last & (1 << j)) > 0) ++bcnt;
}
if (bcnt <= 1) {
ans = max(ans, i - cnt[0]);
} else {
for (int j = 0; j < 10; ++j) {
int nlast = last ^ (1 << j);
ans = max(ans, i - cnt[nlast]);
}
}
if (cnt[last] == 0x3f3f3f3f) cnt[last] = i;
}
return ans;
}
};class Solution {
public:
int longestAwesome(string s) {
int cnt[1 << 10], last = 0, ans = 0;
memset(cnt, 0x3f, sizeof cnt);
cnt[0] = -1;
for (int i = 0; i < s.size(); ++i) {
last ^= (1 << (s[i] - '0'));
for (int j = 0; j < 10; ++j) {
int nlast = last ^ (1 << j);
ans = max(ans, i - cnt[nlast]);
}
cnt[last] = min(cnt[last], i);
ans = max(ans, i - cnt[last]);
}
return ans;
}
};复杂度分析
时间复杂度：O(K * N) K 为字符种类，N为字符长度
空间复杂度：O(2 ^ K)
参考
[1]. LeetCode 原题. https://leetcode-cn.com/problems/find-longest-awesome-substring
本文为原创文章，欢迎分享，勿全文转载，如果内容你实在喜欢，可以加入收藏夹，说不定哪天故事又继续更新了呢。 本文地址：https://qoogle.top/xiaoxu-turorial-leetcode-1542-find-longest-awesome-substring/
留言