1542. 找出最长的超赞子字符串
题目描述
给你一个字符串 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
仅由数字组成
解法
方法一:状态压缩 + 前缀和思想
根据题目描述,“超赞子字符串”中的字符可以通过交换得到回文字符串,因此,“超赞子字符串”中最多有一个数字字符出现奇数次,其余数字字符出现偶数次。
我们可以用一个整数 $st$ 来表示当前前缀字符串中数字字符出现的奇偶性,其中 $st$ 的第 $i$ 位表示数字字符 $i$ 出现的奇偶性,即 $st$ 的第 $i$ 位为 $1$ 表示数字字符 $i$ 出现奇数次,为 $0$ 表示数字字符 $i$ 出现偶数次。
而如果子字符串 $s[j,..i]$ 是“超赞字符串”,那么前缀字符串 $s[0,..i]$ 的状态 $st$ 与前缀字符串 $s[0,..j-1]$ 的状态 $st'$ 的二进制位中,最多只有一位不同。这是因为,二进制位不同,表示奇偶性不同,而奇偶性不同,就意味着子字符串 $s[j,..i]$ 中该数字出现的次数为奇数次。
所以,我们可以用哈希表或数组记录所有状态 $st$ 第一次出现的位置。若当前前缀字符串的状态 $st$ 在哈希表中已经存在,那么说明当前前缀字符串的状态 $st$ 与前缀字符串 $s[0,..j-1]$ 的状态 $st'$ 的二进制位中,所有位都相同,即子字符串 $s[j,..i]$ 是“超赞字符串”,更新答案的最大值。或者,我们可以枚举每一位,将当前前缀字符串的状态 $st$ 的第 $i$ 位取反,即 $st \oplus (1 << i)$,然后判断 $st \oplus (1 << i)$ 是否在哈希表中,若在,那么说明当前前缀字符串的状态 $st$ 与前缀字符串 $s[0,..j-1]$ 的状态 $st' \oplus (1 << i)$ 的二进制位中,只有第 $i$ 位不同,即子字符串 $s[j,..i]$ 是“超赞字符串”,更新答案的最大值。
最后,返回答案即可。
时间复杂度 $O(n \times C)$,空间复杂度 $O(2^C)$。其中 $n$ 和 $C$ 分别为字符串 $s$ 的长度和数字字符的种类数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|