每日一题：找出最长的超赞子字符串

题意

给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。

「超赞子字符串」需满足满足下述两个条件：

该字符串是 s 的一个非空子字符串

进行任意次数的字符交换重新排序后，该字符串可以变成一个回文字符串

Solution

首先，一个字符串可以重新排序得到一个回文字符串的充要条件是：对字符计数，出现奇数次的字符个数小于等于1。

由此我们可以发现：我们没有必要知道这个数字到底出现了几次，我们只需要关心它到底是出现了奇数次还是偶数次。我们用 $0,1$ 来表示出现了 $偶数/奇数$ 次，由于需要统计的字符只有 $0-9$ 十个数字，因此我们只需要一个十位的二进制数 $status$ 即可表示当前所有字符出现次数的奇偶状态，即第i位表示数字 $i$ 出现次数的奇偶性。

假设当前遇到的数字是 i ，那么更新它的状态就是 $status ^= (1 << i)$ ，因为根据异或的特性，相同为0，不同为1，能够很好的实现我们需要的 $奇+奇(1+1)=偶+偶(0+0)=偶(0),奇+偶(1+0)= 偶+奇(0+1)=奇(1)$，改变对应二进制位的状态。

我们遍历字符串维护这样一个 $status$，采用数组标记的思想，$pre[status]$ 表示 $status$ 出现的最早位置。

满足超赞字符串的条件：

1. 再一次遇到之前已经出现过的 $status$ ，说明所有数字都出现了偶数次。（因为每一位二进制位的奇偶性都相同的话，不论都是1还是0，$奇-奇=偶-偶=偶$，都代表这些字符在中间这一段出现了偶数次，长度为 $当前位置i - 最早出现的位置pre[status]$）

2. 与之前出现过的 $status$ 只有一个二进制位不同，说明这个不同的二进制位出现了奇数次 $(奇-偶=偶-奇=奇)$，其余的二进制位出现了偶数次，仍然满足回文字符串的条件。针对这种情况，我们只需要从 $0-9$ 枚举二进制位，然后看之前是否出现过即可，同时维护答案。

Code

class Solution {
    static int[] pre = new int[1 << 11];
    public int longestAwesome(String s) {
        int n = s.length(), status = 0, res = 0;
        Arrays.fill(pre, -2);  // pre数组初始化为-2，代表都没有出现过
        pre[status] = -1;  // 最初的状态为0，代表都出现了0次（偶数次）
        for (int i = 0; i < n; i++) {
            status ^= 1 << (s.charAt(i) - '0');  // 更新当前状态
            if (pre[status] != -2) {  // 之前已经存在过
                res = Math.max(res, i - pre[status]);
            } else {  // 没有存在过
                pre[status] = i;
            }
            for (int j = 0; j < 10; j++) {  // 枚举0-9
                int status1 = status ^ (1 << j);  // 将对应位置的奇偶性改变
                if (pre[status1] != -2) {  // 之前是否出现过
                    res = Math.max(res, i - pre[status1]);
                }
            }
        }
        return res;
    }
}