542. 找出最长的超赞子字符串 [hard]

https://leetcode-cn.com/problems/find-longest-awesome-substring/

给你一个字符串 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,343 | 提交次数3,986

First Try

2020-09-02

周赛hard题目，除了暴力法统计奇偶没有其他思路，暴力法直接超时。

对于自由度过高的策略除了遍历总是难以下手，看了官方解答，需要结合s都是数字和前缀和变种才能搞定。

s仅由数字组成，这个提示竟然是关键因素，说明如果存在一个不同，仅需要遍历10次。

然后考虑前缀和的变种，考虑一个10位长的数字，对于每一位代表该位数字的奇偶数统计，偶数次为0奇数次为1，该数字其实最大只有1023。如果s[i:j]是超赞字符串，那么s[0:i - 1]和s[0: j]最多只在一个数字位上的统计有区别。

如果完全相同，则取出最小index的前缀进行计算。如果只有1个不同，则遍历10次查找是否存在仅有1个不同的前缀，计算index之差作为长度。遍历完返回最大index之差为答案。

如果不是经常做题有手感，这种题对新手而言除了暴力法真的很难想到前缀法。

class Solution:
    def longestAwesome(self, s: str) -> int:


        prefix_idx = {0: -1}  # 起始位为-1，这样至少idx为0的时候回文长度为1
        palin = 0 
        rv = 0 
        for idx, c in enumerate(s):
            palin ^= (1 << int(c))   # 仅对第c位进行置换操作，1变为0，0变为1， 其实用tuple也行
             # 如果前面存在完全相同的排列统计
            if palin in prefix_idx: 
                rv = max(rv, idx - prefix_idx[palin])
            else:
                prefix_idx[palin] = idx # 只保留最早出现的idx
            # 如果前面存在仅相差一个字母的统计，遍历所有可能，总共有10个可能
            for i in range(10):
                tmp_palin = palin ^ (1 << i)
                if tmp_palin in prefix_idx:
                    rv = max(rv, idx - prefix_idx[tmp_palin])
        return rv 

执行用时：1616 ms, 在所有 Python3 提交中击败了68.05%的用户
内存消耗：14.1 MB, 在所有 Python3 提交中击败了36.55%的用户

542. 找出最长的超赞子字符串 [hard]​

First Try​

542. 找出最长的超赞子字符串 [hard]

First Try