题目

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

解题思路分析

1、前缀和+位运算；时间复杂度O(n)，空间复杂度O(1)

func longestAwesome(s string) int {
   res := 0
   n := len(s)
   m := make(map[int]int) // 保存每个状态第1次出现的下标
   m[0] = -1              // 0对应的下标
   cur := 0
   for i := 0; i < n; i++ {
      value := int(s[i] - '0')
      cur = cur ^ (1 << value)
      if index, ok := m[cur]; ok { // 相同的情况
         res = max(res, i-index)
      } else {
         m[cur] = i
      }
      for j := 0; j < 10; j++ { // 相差1位的情况
         if index, ok := m[cur^(1<<j)]; ok {
            res = max(res, i-index)
         }
      }
   }
   return res
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

总结

Hard题目，题目跟leetcode 1915.最美子字符串的数目 类似，都是采用前缀和+位运算