---

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

• 标签：位运算、哈希表、字符串
• 难度：困难

题目链接

• 1542. 找出最长的超赞子字符串 - 力扣

题目大意

描述：给定一个由数字组成的字符串 $s$。

要求：返回 $s$ 中最长的"超赞子字符串"的长度。超赞子字符串是指一个字符串，可以重新排列为回文字符串。

说明：

• $1 \le s.length \le 10^5$。
• $s$ 只包含数字字符 $0 \sim 9$。

示例：

• 示例 1：

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

• 示例 2：

输入：s = "12345678"
输出：1

解题思路

思路 1：位运算 + 哈希表

1. 核心思想

一个字符串能重排成回文串的充要条件：最多只有一个字符出现奇数次。

在子字符串中，字符出现的奇偶性是关键信息。我们可以用一个 $10$ 位的二进制掩码表示前缀 $s[0..i]$ 中各数字的奇偶性（第 $d$ 位为 $1$ 表示数字 $d$ 出现奇数次）。

设 $mask[i]$ 为前缀 $s[0..i]$ 的奇偶性掩码，则子串 $s[l+1..r]$ 的奇偶性掩码为 $mask[r] \oplus mask[l]$。

子串可以重排为回文串 $\iff$ 其奇偶性掩码中 $1$ 的个数 $\le 1$。

问题转化为：找到最长的子串 $[l+1, r]$，使得 $mask[r] \oplus mask[l]$ 中 $1$ 的个数 $\le 1$。等价于 $mask[r] \oplus mask[l]$ 为 $0$ 或 $2$ 的幂。

2. 具体步骤

第 1 步：初始化哈希表 $first\_pos$，记录每个掩码第一次出现的位置（索引 $i$，$i$ 从 $0$ 到 $n$，其中 $mask[0] = 0$）。

第 2 步：遍历 $s$，更新 $mask$。

第 3 步：对于当前 $mask$：

• 如果 $mask$ 之前出现过，则子串长度 = $i - first\_pos[mask]$（该子串中所有字符出现偶数次，可以排成回文）。
• 对于每个 $d \in [0, 9]$，检查 $mask \oplus (1 << d)$ 是否出现过。若出现过，则子串中有一个字符出现奇数次（即 $d$），其余为偶数次，长度 = $i - first\_pos[mask \oplus (1 << d)]$。
• 更新最大值。

第 4 步：如果 $mask$ 不在哈希表中，记录当前位置。

3. 举例说明

以 $s = "3242415"$ 为例：

遍历过程：

i  char  mask(二进制)    考察
0  '3'   0000001000      首次出现
1  '2'   0000001100      首次出现
2  '4'   0000010100      首次出现
3  '2'   0000011000      mask 首次出现在 i=0？不匹配。检查掩码差一位：
                         0000011000 ^ 0000010000 = 0000001000(8) 出现在 i=0 → 长度 3
4  '4'   0000001000      mask 出现在 i=0 → 长度 4
5  '1'   0000001010      首次出现
6  '5'   0000011010      检查 0000011010 ^ 0000001010 = 0000010000(16) 出现在...等等
                         实际要检查所有一位差异

最终最长超赞子串长度为 $6$。

4. 关键优化

• 掩码只有 $2^{10} = 1024$ 种可能，哈希表最多存储 $1024$ 个键。
• 每次检查 $10$ 种一位差异，总复杂度 $O(10 \times n) = O(n)$。

思路 1：代码

class Solution:
    def longestAwesome(self, s: str) -> int:
        # 记录每个掩码第一次出现的位置
        first_pos = {0: -1}  # 前缀为空时 mask=0，位置为 -1
        mask = 0
        ans = 0

        for i, ch in enumerate(s):
            d = int(ch)
            mask ^= (1 << d)  # 翻转第 d 位的奇偶性

            # 情况 1：所有字符出现偶数次
            if mask in first_pos:
                ans = max(ans, i - first_pos[mask])
            else:
                first_pos[mask] = i

            # 情况 2：一个字符出现奇数次，其余偶数次
            for j in range(10):
                target = mask ^ (1 << j)
                if target in first_pos:
                    ans = max(ans, i - first_pos[target])

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(10 \times n) = O(n)$。
• 空间复杂度：$O(2^{10}) = O(1)$，掩码数不超过 $1024$。

---

思路 2：数组代替哈希表

由于掩码范围是 $[0, 1024)$，可以用数组代替哈希表以获得更快的速度。

class Solution:
    def longestAwesome(self, s: str) -> int:
        first_pos = [-1] * 1024
        first_pos[0] = -1
        mask = 0
        ans = 0

        for i, ch in enumerate(s):
            mask ^= (1 << (ord(ch) - ord('0')))

            if first_pos[mask] != -1:
                ans = max(ans, i - first_pos[mask])
            else:
                first_pos[mask] = i

            for j in range(10):
                target = mask ^ (1 << j)
                if first_pos[target] != -1:
                    ans = max(ans, i - first_pos[target])

        return ans

思路 2：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1024) = O(1)$。