LeetCode 题解工作台
找出最长的超赞子字符串
给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。 「超赞子字符串」需满足满足下述两个条件： 该字符串是 s 的一个非空子字符串 进行任意次数的字符交换后，该字符串可以变成一个回文字符串 示例 1： 输入： s = "3242415" 输出： 5 解释： "24241" 是最长的超赞…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 哈希·表·结合·string
答案摘要
根据题目描述，“超赞子字符串”中的字符可以通过交换得到回文字符串，因此，“超赞子字符串”中最多有一个数字字符出现奇数次，其余数字字符出现偶数次。 我们可以用一个整数 来表示当前前缀字符串中数字字符出现的奇偶性，其中 的第 位表示数字字符 出现的奇偶性，即 的第 位为 表示数字字符 出现奇数次，为 表示数字字符 出现偶数次。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·表·结合·string 题型思路
题目描述
给你一个字符串 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仅由数字组成
解题思路
方法一：状态压缩 + 前缀和思想
根据题目描述，“超赞子字符串”中的字符可以通过交换得到回文字符串，因此，“超赞子字符串”中最多有一个数字字符出现奇数次，其余数字字符出现偶数次。
我们可以用一个整数 来表示当前前缀字符串中数字字符出现的奇偶性，其中 的第 位表示数字字符 出现的奇偶性，即 的第 位为 表示数字字符 出现奇数次，为 表示数字字符 出现偶数次。
而如果子字符串 是“超赞字符串”，那么前缀字符串 的状态 与前缀字符串 的状态 的二进制位中，最多只有一位不同。这是因为，二进制位不同，表示奇偶性不同，而奇偶性不同，就意味着子字符串 中该数字出现的次数为奇数次。
所以，我们可以用哈希表或数组记录所有状态 第一次出现的位置。若当前前缀字符串的状态 在哈希表中已经存在，那么说明当前前缀字符串的状态 与前缀字符串 的状态 的二进制位中，所有位都相同，即子字符串 是“超赞字符串”，更新答案的最大值。或者，我们可以枚举每一位，将当前前缀字符串的状态 的第 位取反，即 ，然后判断 是否在哈希表中，若在，那么说明当前前缀字符串的状态 与前缀字符串 的状态 的二进制位中，只有第 位不同，即子字符串 是“超赞字符串”，更新答案的最大值。
最后，返回答案即可。
时间复杂度 ，空间复杂度 。其中 和 分别为字符串 的长度和数字字符的种类数。
class Solution:
def longestAwesome(self, s: str) -> int:
st = 0
d = {0: -1}
ans = 1
for i, c in enumerate(s):
v = int(c)
st ^= 1 << v
if st in d:
ans = max(ans, i - d[st])
else:
d[st] = i
for v in range(10):
if st ^ (1 << v) in d:
ans = max(ans, i - d[st ^ (1 << v)])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each character is processed once with constant-time mask and hash operations. Space complexity is O(2^10) due to storing first occurrences for all possible 10-bit masks representing digit parities. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you tracking character counts efficiently to evaluate palindrome potential?
- question_mark
Consider using a hash table to avoid redundant substring checks and speed up comparisons.
- question_mark
Think about bitmasking to condense digit parity states and simplify palindrome verification.
常见陷阱
外企场景- error
Failing to check masks differing by one bit, which allows for a central odd digit in palindromes.
- error
Using nested loops to check all substrings, which leads to timeouts on large inputs.
- error
Not initializing the hash table for mask zero, which misses substrings starting at index 0.
进阶变体
外企场景- arrow_right_alt
Find the number of awesome substrings instead of the longest one, counting all valid segments.
- arrow_right_alt
Adapt the problem to alphabetic strings, tracking character counts with a larger bitmask or array.
- arrow_right_alt
Find the longest substring forming a k-palindrome, allowing up to k mismatches in the bitmask.