问题

如果一个字符串中所有元素出现的次数均为偶数次,则称该字符串为偶数字符串,例如字符串 “aabbcc” 为偶数字符串,“abcc” 不是偶数字符串,空串被认为是偶数字符串。现给定由小写字母组成的字符串 S,找出 S 的连续子串中的最长偶数字符串并给出其长度。

示例 1

输入:S = "golangisugly"
输出:0

示例 2

输入:S = "bettercallsaul"
输出:4

分析

对于本问题,最直观的解法是暴力遍历字符串 S 的所有子串,找到满足偶数字符串条件的最长子串并返回其长度即可。

public int BruteForce(String S) {
    int n = S.length();
    int[] preXOR = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        preXOR[i] = (S.charAt(i - 1) - 'a') ^ (preXOR[i - 1]);
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if ((preXOR[j] ^ preXOR[i - 1]) == 0) {
                res = Math.max(res, j - i + 1);
            }
        }
    }
    return res;
}

这里采用了异或前缀数组来加速判断子串是否为偶数字符串:对于子串 s,如果其为偶数字符串,那么对子串 s 中所有元素进行异或的最终结果会是 0,比如对于子串 s = “ette”,子串中所有元素进行异或后的结果 e ^ t ^ t ^ e = 0。此外,对于子串 s = S[i, j],根据异或运算的性质有 S[i] ^ S[i + 1] ^ … ^ S[j] = S[j] ^ S[i - 1]。易得上述暴力算法的时间复杂度为$O(n^2)$,难以适用于长度较大的字符串。

算法优化

现在我们已经通过异或前缀数组加速了偶数字符串的判断速度,注意到暴力算法最耗时之处在于需要遍历所有子串,我们可以再进一步利用异或数组来减少子串的遍历:对于字符串 S,我们在遍历时记录其前缀数组当前数值 K 首次出现时的索引 i,根据异或运算的性质,假设在遍历到索引 j 时异或前缀 K 再次出现,那么则有 S[0] ^ S[1] ^ … ^ S[i] ^ S[i + 1] ^ S[i + 2] ^ … ^ S[j] = K,又由于 S[0] ^ S[1] ^ … ^ S[i] = K,那么则有 K ^ S[i + 1] ^ S[i + 2] ^ … ^ S[j] = K,即 S[i + 1] ^ S[i + 2] ^ … ^ S[j] = 0。考虑到偶数字符串所有元素异或后的值为 0,因此在前缀 K 二次出现时可以认为子串 S[i + 1, j] 为偶数字符串,此时我们只需要在遍历字符串 S 的过程中记录当前异或前缀第一次出现的下标 i 与异或前缀 num,按照上述规则判断偶数字符串并更新满足条件的最长连续子串长度即可,易得该算法的时间复杂度为$O(n)$。

public int findTheLongestEvenSubstring(String S) {
    int num = 0, res = 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, 0);
    for (int i = 0; i < S.length(); i++) {
        num ^= 1 << (S.charAt(i) - 'a');
        map.putIfAbsent(num, i + 1);
        if (map.containsKey(num)) {
            res = Math.max(res, i - map.get(num) + 1);
        }
    }
    return res;
}