JZX轻语：简
LeetCode 1542 - 找出最长的超赞字符串
发表于2024年05月20日
相当有挑战性的题目。朴素的前缀和做法是使用一个数组pre，其中pre[i] = (c0, ..., c9)是指数组arr前i个元素中，0-9的计数，所以子数组arr[i..j]的计数信息可通过pre[j + 1] - pre[i + 1]计算可得。若子数组满足超赞字符串(重排后满足回文)，则计数信息需要满足仅存在零个或一个奇数计数位。因此，遍历所有的位次，计算前缀信息后再遍历以该元素结尾的子数组，校验是否为超赞字符串，不断更新超赞字符串的最长长度。
但这样会发生超时，我们可以将计数信息压缩到一个int，其中第i个二进制位表示数字i的计数的奇偶性。其中pre[j] - pre[i]可以表示为pre[j] ^ pre[i](使用异或来表示奇偶相减)，然后判断为1的位个数是否小于等于1即可。
但还是会超时…需要再通过逆向思维来挖掘可以优化的地方：在前面的做法中，每遍历一个位次时，均需要通过双重循环，计算以该位次元素结尾的子数组中满足要求(即两个前缀信息异或后得到子数组计数信息，判断1的个数小于等于1)的最长长度，复杂度为O(n^2)。不难得知，可能的前缀信息共有1024个，其中满足和当前前缀异或后的结果中。1的个数小于等于1的前缀信息共11个(即和本身异或，得到全0比特串，或者和0000000001，0000000010直至100000000异或，得到只有一个1的比特串)。我们可以使用哈希表记录这些前缀信息第一次出现的位置(后面出现的位置拿来比较没意义了，只有和第一次出现的位置比较才会得到比较长的子数组)，然后反向推导，根据当前位次的前缀信息比特串来得到异或后满足要求的这11个比特串，然后查哈希表得到它们第一次出现的位置，更新结果即可！
class Solution:
def longestAwesome(self, s: str) -> int:
prev_sum = [0] * (len(s) + 1)
prev_sum_map = {0: 0}
ans = 0
for i, ch in enumerate(s):
ch = int(ch)
prev_sum[i + 1] = prev_sum[i] ^ (1 << ch)
if prev_sum[i + 1] not in prev_sum_map:
prev_sum_map[prev_sum[i + 1]] = i + 1
else:
l = i + 1 - prev_sum_map[prev_sum[i + 1]]
ans = max(l, ans)
for j in range(10):
# 构造00..100.., 其中唯一的1在第j个位置
mask = 1 << j
first_prefix = mask ^ prev_sum[i + 1]
if first_prefix in prev_sum_map:
l = i + 1 - prev_sum_map[first_prefix]
ans = max(l, ans)
return ans