type
status
date
slug
summary
tags
category
icon
password
题目：找出最长的超赞子字符串
「超赞子字符串」需满足满足下述两个条件：
- 该字符串是
s的一个非空子字符串
- 进行任意次数的字符交换后，该字符串可以变成一个回文字符串
示例 1：
示例 2：
示例 3：
示例 4：
提示：
1 <= s.length <= 10^5
s仅由数字组成
题解
思路
要找出最长的超赞子字符串，我们可以采用位掩码和哈希表的方法。这个方法的核心思想是利用位掩码来跟踪字符串中每个字符出现次数的奇偶性，因为一个字符串要变成回文字符串，每个字符出现的次数要么是偶数，要么只有一个字符出现次数是奇数。
步骤如下：
- 初始化一个变量state为0，用于表示当前的位掩码状态。
- 初始化一个哈希表firstOccurrence，用来存储每个位掩码状态第一次出现的位置，初始时仅包含{0: -1}，表示空字符串的状态。
- 遍历字符串s，对于每个字符，更新state的值。这里我们将字符转换为0到9的数字，然后使用1 << (字符 - '0')来更新state。
- 对于每个更新后的state，如果它之前出现过（在firstOccurrence中可以找到），则计算当前位置与第一次出现位置的距离，更新最长超赞子字符串的长度。
- 同时，为了处理最多只有一个字符出现次数为奇数的情况，我们尝试将state的每一位翻转（表示添加或移除一个字符），看看翻转后的状态是否出现过，如果出现过，也更新最长长度。
- 遍历结束后，返回记录的最长长度。
代码
附录
- Author:Zinphy
- URL:https://zouysay.cn/article/7b3c2f0a-e100-4245-aa3b-3935d32d16b5
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!