题目描述

给你一个字符串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 仅由数字组成

思路:(对子串的奇偶性进行状态压缩 思路参考:zerotrac2)

一个字符串是否能够通过位置交换变成一个回文串

• 取决于该字符串中每个字符出现次数的奇偶性
• 要么全部出现偶数次，要么当且仅当只有一个字符出现奇数次，其他字符串出现偶数次

如何统计一个子串S[i…j]间每个字符出现的次数是奇数还是偶数

• 我们用二进制来表示这个字符的出现次数是偶数(0)还是奇数(1)
• 记录一个前缀和prefix[i]:表示以i结尾的子串每个字符出现次数的奇偶性
• 那么S[i…j]之间字符出现次数的奇偶性就是 prefix[j] ^ prefix[i-1]
  • 异或操作刚好满足:奇-奇=偶(1^1 = 0),奇-偶=奇(1^0=1),偶-偶=偶(0^0=0)
• 我们用一个HashMap<Integer,Integer> hash 来记录{key}->prefix[i],{val}->第一次出现该前缀和的位置i
  • 本题中也可以使用一个长度为1<<10的数组来存，但是如果改成26个字母数组就存不下了
• 遍历字符串，对于当前i找到第一个满足条件的j来更新答案
• 找答案的时候分两种情况(prefix[i]和prefix[j-1]最多只有一位不同)
  • 1.prefix[i] == prefix[j] 那么异或后全为偶数
  • 2.S[i…j]中某一个字符出现了奇数次(依次翻转每一位进行判断)
• 注意事项:
  • 我们需要初始化hash.put(0,-1) 因为计算S[0…i]的时候需要用到-1,此时-1没字符视为0

时间复杂度(扫描一次字符串O(N))

代码

class Solution {
    public int longestAwesome(String s) {
        int n = s.length();
        Map<Integer,Integer> hash = new HashMap<>();
        //初始化
        hash.put(0,-1);
        int prefix = 0;
        int ans = 0;
        for(int i = 0 ; i < n ; i++){
            int d = s.charAt(i) - '0';
            //计算以i结尾的前缀
            prefix ^= (1<<d);
            if(hash.containsKey(prefix)){
                //说明前面有相同的prefix进行匹配
                ans = Math.max(ans,i-hash.get(prefix));
            }else{
                //说明该prefix第一次出现
                hash.put(prefix,i);
            }
            for(int j = 0 ; j < 10 ; j++){
                //计算情况2:只有一个字符出现了奇数次
                prefix ^= (1<<j);
                if(hash.containsKey(prefix)){
                    ans = Math.max(ans,i - hash.get(prefix));
                }
                prefix ^= (1<<j);
            }
        }
        return ans;
    }
}