题目描述

给定一个字符串 s。漂亮子串 指的是一个 s 的非空子串，满足进行任意次数的字符交换后，该字符串可以变成一个回文字符串。

请返回 s 中最长的 漂亮子串 的长度。

样例

输入：s = "3242415"
输出：5
解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"。

输入：s = "12345678"
输出：1

输入：s = "213123"
输出：6
解释："213123" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "231132"。

输入：s = "00"
输出：2

限制

• 1 <= s.length <= 10^5
• s 仅由数字组成。

算法

(哈希表，前缀和) $O(n)$

1. 只关注每种数字出现次数的奇偶性，故共有 $2^{10}$ 种组合方式。组成回文串的条件就是最多只有一种数字出现次数为奇数。
2. 维护一个哈希表，记录每种组合方式（用二进制表示）最早出现的位置。初始时，mp[0] = -1。维护一个每种数字出现次数的二进制值，初始为 0。
3. 遍历时，当前数位 $s(i)$ 上的二进制值取反。枚举每一个数位，如果当前数位取反后，在哈希表中能查到值为 p，则说明 [p + 1, i] 区间可以构成回文串。如果当前二进制值本身也在哈希表中出现过，记为 p，则也说明 [p + 1, i] 可以构成回文串。如果没出现过，则记录到哈希表中。

时间复杂度

• 每个位置仅枚举 10 个数位，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(2^{10})$ 的空间存储哈希表，可以视为常数。

Go 代码

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func longestAwesome(s string) int {
    mp := make(map[int]int)
    mp[0] = -1

    var cur, ans int
    for i, v := range s {
        cur ^= 1 << (v - '0')
        for j := 0; j < 10; j++ {
            if last, ok := mp[cur ^ (1 << j)]; ok {
                ans = max(ans, i - last)
            }
        }

        if last, ok := mp[cur]; ok {
            ans = max(ans, i - last)
        } else {
            mp[cur] = i
        }
    }

    return ans
}