https://leetcode.cn/problems/find-longest-awesome-substring/description/
题目 #
给你一个字符串 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仅由数字组成
题解 #
一个子串要互文，由于元素位置可以随意互换，因而元素位置并不重要，元素个数才重要。 更确切来说，元素个数的奇偶性才重要，由于互文是左右对称的，只有最中间的那一个元 素（长度为奇数时）才可能落单。
由于字符串中只有数字字符，即只有 0~9, 我们要表征各个字符出现次数的奇偶性(0/1), 完全可以使用状态压缩。即对应的 ith 比特位为 0 则为偶， 1 则为奇。我们将这样的 一个状态存放在 mask 中。
之后我们从左向右遍历，对于当前的数字字符 c, 我们通过计算 mask ^= 1 << c便得到了从下标 0 到当前位置的子串中各个字符出现次数的奇偶性。
以上内容都还比较容易想到，关键在于发现以下性质：
当我们知道了 0~i 的 mask 为 mask[i], 0~j 的 mask 为 mask[j], 若满足以下之一的条件，则 i+1~j 对应的子串可组成互文串。
mas[i] == mask[j]i+1~j中所有字符出现次数都为偶数次mask[j]仅有一个 bit 位不同i+1~j中仅有一个字符出现次数为奇数次
整体解决思路为，从左向右遍历，把当前下标作为子串的结尾，同时维护 mask,对于当前 mask, 我们查看相同的 mask, 以及只差一个比特位的 mask 在之前是否出现，根据下标区间计算互文长度。注意只有当一个 mask 首次出现时，我们才将其记录到 hash 中，以 mask 为 key, 下标为值，重复的 mask 再度出现时我们并不更新下标值，因为我们是基于尾坐标去找头坐标，我们希望头坐标越小， 子数组越长越好。
代码 #
class Solution:
def longestAwesome(self, s: str) -> int:
n = len(s)
ans = 0
hash = {0: -1}
mask = 0
for i in range(n):
c = s[i]
mask ^= (1 << int(c))
if mask in hash:
ans = max(ans, i - hash[mask])
else:
hash[mask] = i
for b in range(10):
pairMask = mask ^ (1 << b)
if pairMask in hash:
ans = max(ans, i - hash[pairMask])
return ans