1542. 找出最长的超赞子字符串 哈希+状态压缩

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 仅由数字组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-longest-awesome-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 做题结果

成功，这要感谢灵神的构造题，这种题渐渐的也有点思路了

方法：哈希+状态压缩

特别需要注意的一点是，能否形成回文串，实际上是有两种情况，一种是长度奇数一种是长度偶数

1. 长度是偶数：那每个字符的长度都是偶数

2. 长度是奇数：中间的一个字符，长度是奇数，其他都是偶数

那我们就有个重要的方向：关注字符串的奇偶性。

1. 前面的字符串能找到和当前字符串奇偶性相同的情况，则两段相减，得到每个字符都是偶数，相减就可以找到长度偶数串；

2. 前面的字符串形成的奇偶性，和当前差一位的情况，我们拿到当前的奇偶性，取反其中的一位，就可以找到长度为奇数的字符串

3. 由于我们希望字符串尽可能的长，所以首次找到某个 key 之后，后续不再替换

4. 奇偶性可用位运算的 1 和 0 来标识，前缀的方式求奇偶性

class Solution {
    public int longestAwesome(String s) {
        long v = 0;
        Map<Long,Integer> map = new HashMap<>();//奇偶性->位置
        map.put(v,-1);
        int n = s.length();
        int ans = 0;
        for(int i =0 ; i < n; i++){
            int index = s.charAt(i)-'0';
            v = v ^ ((long)1<<index);
            ans = Math.max(ans,i-map.getOrDefault(v,i));
            for(int j = 0; j < 10; j++){
                long diff = (v ^ ((long)1<<j));
                ans = Math.max(ans,i-map.getOrDefault(diff,i));
            }
            if(!map.containsKey(v)) map.put(v,i);
        }
        return ans;
    }
}