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

大家好，欢迎来到IT知识分享网。

题目链接

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

题目描述

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

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

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

示例 1：

输入：s = “”
输出：5
解释：“24241” 是最长的超赞子字符串，交换其中的字符后，可以得到回文 “24142”

示例 2：

示例 3：

输入：s = “”
输出：6
解释：“” 是最长的超赞子字符串，交换其中的字符后，可以得到回文 “”

示例 4：

提示：

• $1\le s.length\le 10^5$
• $s$ 仅由数字组成

解法：状态压缩 + 哈希表

如果一个子串，在进行任意次的字符交换之后，能够变成回文串，说明子串中出现奇数次的字符最多只有一个。

又由于 $s$ 是由 $0\sim 9$ 的数字组成的，所以我们直接用一个 $10$ 位的二进制数来表示对应数字字符的出现次数。

• 如果该位是 $0$ ，则说明出现了偶数次；
• 如果该位是 $1$ ，则说明出现了奇数次；

比如 "134" ，对应的二进制数就是 $(1101{)}_2=13$。

接着我们使用哈希表来记录其第一次出现的位置（因为我们要求的是最大值，所以只用记录越前面的位置越好，所以直接记录第一次的位置即可）。

我们假设 区间$[j+1,i]$子串 是一个超赞子字符串。

我们用 $f$ 表示子串对应的二进制数。

那么 $f(0,i)$ 和 $f(0,j)$ 最多只有一位数不同。

因为 $f(j,i)$ 相当于是 $f(0,i)-f(0,j)$，因为 区间$[j+1,i]$子串 是一个超赞子字符串，那么 $f(j,i)$ 最多就只有一位是 $1$ ，其他的都是 $0$。

如此一来，我们就可以分开讨论：

• 当 $f(0,i)=f(0,j)$ 的情况；
• 当 $f(0,i)-f(0,j)=1^{\prime }$ 的情况；

我们用 $mask$ 来记录 区间$[0,i]$ 字符的出现情况。

1.当 $f(0,i)=f(0,j)$ 的情况；

如果 哈希表$mp$ 里有 $mask$ 的记录，那么 $j=mp[mask]$，说明 $f(0,j)=f(0,i)=mask$，即 $[0,j]$ 和 $[0,i]$ 字符的出现情况一样，$[j+1,i]$ 就是一个超赞子字符串。 接着再更新答案，$ans=max(ans,i-j)$。

否则就说明第一次出现 $mask$ 这样的情况，记录到哈希表中 $mp$ 中，即 $mp[mask]=i$。

2.当 $f(0,i)-f(0,j)=1^{\prime }$ 的情况；

直接从 $0\sim 9$ 枚举与 $mask$ 相差一位的情况，求最大值。逻辑和第一种情况一样。

时间复杂度： $O(n\times 10)$

C++代码：

class Solution { 
    public: int longestAwesome(string s) { 
    int n = s.size() , ans = 0; unordered_map<int,int> mp{ 
   { 
   0,-1}}; int mask = 0; for(int i = 0;i < n;i++){ 
    int k = s[i] - '0'; mask ^= (1 << k); auto it = mp.find(mask); //完全匹配 if(it != mp.end()){ 
    auto j = mp[mask]; ans = max(ans , i - j); } else mp[mask] = i; //差了一个字符 for(int p = 0;p < 10;p++){ 
    int t = mask ^ (1 << p); if(mp.find(t) != mp.end()){ 
    auto j = mp[t]; ans = max(ans , i - j); } } } return ans; } };