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

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^5

s 仅由数字组成

题解

一个子串要互文，由于元素位置可以随意互换，因而元素位置并不重要，元素个数才重要。更确切来说，元素个数的奇偶性才重要，由于互文是左右对称的，只有最中间的那一个元素（长度为奇数时）才可能落单。

由于字符串中只有数字字符，即只有 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