难度: Hard
给你一个字符串 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^5s 仅由数字组成运行时间: 165 ms
内存: 17.4 MB
class Solution:
def longestAwesome(self, s: str) -> int:
wei = {str(x):2**x for x in range(10)}
r = [0] + list(wei.values())
a = {0:-1}
b = defaultdict(int)
res = 0
ss = [wei[x] for x in s]
for i,x in enumerate(ss):
res = res ^ x
if res in a:
b[res] = max(b[res],i)
else:
a[res] = i
b[res] = i
return max(b[x ^ j] - a[x] for x in a for j in r)
这个题解的核心思路是使用位掩码来表示字符串s中每个位置上数字字符出现的奇偶性。首先，为每个数字0到9分配一个唯一的二进制位，使用异或操作来更新当前的位掩码。这个位掩码代表了从字符串开始到当前位置的所有字符的奇偶状态。如果两个位置的位掩码相同，或者位掩码相差一个二进制位（即只有一个数字的奇偶性不同），那么这两个位置之间的子字符串是一个超赞子字符串。该方法使用哈希表记录每个位掩码第一次出现的位置，以及该掩码所能达到的最大长度。通过遍历每个可能的掩码，并检查与当前掩码异或后只改变一个位的掩码是否存在，来找到可能的最长超赞子字符串。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def longestAwesome(self, s: str) -> int:
wei = {str(x):2**x for x in range(10)} # 为每个数字分配一个二进制位
r = [0] + list(wei.values()) # 可能的位掩码变化
a = {0:-1} # 记录位掩码第一次出现的位置
b = defaultdict(int) # 记录位掩码的最大长度
res = 0 # 当前位掩码
ss = [wei[x] for x in s] # 预处理字符串中每个字符对应的位掩码
for i,x in enumerate(ss):
res = res ^ x # 更新当前位掩码
if res in a:
b[res] = max(b[res],i) # 更新当前位掩码的最大长度
else:
a[res] = i # 记录位掩码首次出现的位置
b[res] = i
return max(b[x ^ j] - a[x] for x in a for j in r) # 检查每个位掩码和可能的单位改变，找到最长的超赞子字符串长度
使用位掩码来表示字符的出现奇偶性可以有效地跟踪和更新每个数字字符在字符串中出现的次数是奇数次还是偶数次。每个数字对应一个位，在位掩码中，如果某个位置的位是1，则表示对应的数字出现了奇数次，如果是0，则表示偶数次。这种表示法使得我们能够用一个整数（位掩码）来简洁地表达出所有数字字符的出现奇偶性状态，非常适合进行快速的比较和更新。
异或操作用于更新位掩码时，具有将数字的出现次数从偶数变奇数，或从奇数变偶数的特性。这是因为异或操作对同一个位进行两次相同数值的操作会抵消，即偶数次异或同一个值结果为0（偶数），奇数次结果为该值（奇数）。在本题中，这意味着每次遇到某个数字字符时，通过异或该数字对应的二进制位，可以轻松地更新该数字出现次数的奇偶状态，而无需记录具体的出现次数，从而有效地减少计算和存储需求。
如果两个位置的位掩码完全相同，意味着在这两个位置之间的所有字符的出现次数改变都是偶数次（包括零次），因此这段子字符串中每个数字的出现次数都是偶数次。在超赞子字符串的定义中，最多只有一个数字可以出现奇数次，因此，位掩码完全相同符合超赞子字符串的条件。而如果位掩码相差一个二进制位，表示从一个位置到另一个位置的过程中，只有一个数字的出现次数从偶数变为奇数或从奇数变为偶数，这也符合超赞子字符串的特性，即最多只有一个数字出现奇数次。因此，这种位掩码的差异性也能有效地帮助识别可能的超赞子字符串。