LeetCode 1542. 找出最长的超赞子字符串

2022-02-22 HGNULB 约 10 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1542. 找出最长的超赞子字符串

题意分析

给定一个只含数字字符的字符串，要找出最长的一个子串，使得这个子串在任意重排后可以变成回文串，返回它的长度。「重排后能成回文」是核心定义，不是要求子串本身就是回文。

一个字符多重集能重排成回文，充要条件是出现奇数次的字符最多有一个：长度为偶数时全部字符必须成对，长度为奇数时允许恰好一个字符落单站在正中间。所以题目实际考察的是子串内每个数字出现次数的奇偶性，具体出现了多少次完全不重要。

字符集被限死在 '0' 到 '9' 十个数字上。这个「只有 10 种字符」的约束是最强的信号：十个奇偶标志位可以整体压缩成一个不超过 1024 的整数，而且「最多一个为奇」意味着候选状态只有 1（全偶）+ 10（某一位为奇）= 11 种，可以逐一枚举。

字符串长度可以到 $10^5$，枚举全部子串是 $O(n^2)$ 起步，再加上判定就更慢，所以必须做成一次线性扫描配常数级查询。

边界上，长度为 1 的子串永远合法（单个字符本身就是回文），所以答案至少是 1；另外要求的是最长子串而不是子序列，子串必须连续。

解法：前缀奇偶位掩码

核心思路

最直接的写法是枚举所有左右端点，对每个子串统计十个数字的出现次数，再数一下有多少个是奇数。这样是 $O(n^2 \cdot 10)$，$10^5$ 的长度下毫无希望。

稍作优化可以固定左端点、向右扩展时增量维护计数，降到 $O(n^2)$，但瓶颈没变：每个子串都被单独考察了一次，而子串数量本身就是平方级的。

突破口在于把「子串的奇偶状态」表示成「两个前缀状态的差」。定义 mask[i] 为字符串前 i 个字符中，数字 d 出现次数的奇偶性放在第 d 位上得到的 10 位整数。那么子串 s[l..r] 中数字 d 的奇偶性，就等于 mask[r+1] 与 mask[l] 在第 d 位上的异或。也就是说，子串的整体奇偶状态就是 mask[r+1] ^ mask[l]。

于是「子串可重排成回文」翻译成位运算就是：mask[r+1] ^ mask[l] 的二进制里最多有一个 1。这样的取值只有 11 种——要么是 0，要么是 1 << k（k 从 0 到 9）。反过来说，固定右端点 r 之后，合法的左端点前缀掩码只能是 mask[r+1] 本身或者 mask[r+1] ^ (1 << k) 这 11 个值之一。

因为要的是最长，所以对每个掩码值只需要记住它第一次出现的前缀位置——越靠左的左端点给出的区间越长，后来出现的同值前缀一律没有价值。

不变量因此确定：数组 first[m] 保存掩码值 m 首次出现时的前缀长度（即该前缀对应的下标边界），未出现过则为 -1；first[0] = 0 表示空前缀的掩码是全 0 且位置在 0。扫描到下标 i 时，answer 已经是所有右端点不超过 i 的合法子串的最大长度。

解题步骤

开一个长度为 $2^{10}$ 的数组 first，全部填 -1 表示尚未出现。用定长数组而不是哈希表，是因为掩码取值范围被字符集锁死在 1024 以内，数组的常数远小于哈希。

把 first[0] 置为 0。空前缀的掩码是 0，位置在整个串的最左侧；漏掉它，所有从下标 0 起头的合法子串都会算不出来。

从左到右扫描，读到字符 s[i] 时把它转成数字 d，执行 mask ^= 1 << d。异或恰好实现了「出现次数奇偶翻转」，比维护十个计数器再取模干净得多。

先处理「全偶」这种情况：若 first[mask] 已存在，说明存在一个更靠左的前缀与当前前缀掩码完全相同，两者之间的子串每个数字都出现偶数次，用 (i + 1) - first[mask] 更新答案；若不存在，就把当前前缀位置 i + 1 记进去。这里的 if-else 结构很关键：只有首次出现才记录，后续同值前缀必须让位给更靠左的那个。

再枚举 k 从 0 到 9，取 m2 = mask ^ (1 << k)，对应「恰好数字 k 出现奇数次」。若 first[m2] 存在就用 (i + 1) - first[m2] 更新答案。这一步不做写入，因为 m2 的记录归它自己被当作 mask 时那一轮负责。

位置全部用「前缀长度」而不是「字符下标」表述：当前前缀长度是 i + 1，区间长度就是两个前缀长度之差，这样天然避开了加一减一的偏移问题。

扫描结束返回 answer。因为长度为 1 的子串永远合法，非空输入的答案至少是 1，这一点由 k 恰好等于当前字符时的枚举自动覆盖，不需要特判。

以 s = "3242415" 走一遍：初始 mask = 0、first[0] = 0、answer = 0。读 '3'，mask 变成 0b0001000（第 3 位），first 中没有此值，记 first[8] = 1；枚举翻转一位得到的 11 个候选里，mask ^ (1<<3) = 0 存在于 first 且值为 0，答案更新为 1 - 0 = 1。读 '2'，mask 变成 0b0001100，未出现，记位置 2；翻转第 2 位得 0b0001000 位置 1，答案候选 2 - 1 = 1；翻转第 3 位得 0b0000100 未出现。读 '4'，mask 变成 0b0011100，记位置 3；翻转第 4 位得 0b0001100 位置 2，长度 1。读 '2'，第 2 位被翻回去，mask 变成 0b0011000，记位置 4；翻转第 3 位得 0b0010000 未出现，翻转第 4 位得 0b0001000 位置 1，答案更新为 4 - 1 = 3。读 '4'，mask 变回 0b0001000，而 first[0b0001000] = 1 已存在，答案更新为 5 - 1 = 4；再枚举翻转，翻第 3 位得 0 位置 0，答案更新为 5 - 0 = 5，对应子串 "32424"，其中 3 出现一次、2 和 4 各出现两次，正好一个奇数字符。读 '1'，mask 变成 0b0001010，记位置 6；翻转第 1 位得 0b0001000 位置 1，长度 5，不超过当前答案；翻转第 3 位得 0b0000010 未出现。读 '5'，mask 变成 0b0101010，记位置 7；逐位翻转得到的候选中，0b0001010 在位置 6、0b0100010 与 0b0111010 均未出现，最长仍是 1。扫描结束返回 5。

代码实现

// 两个前缀掩码相同表示区间内所有数字出现次数均为偶数。
class Solution {
    public int longestAwesome(String s) {
        int[] first = new int[1 << 10];
        for (int i = 0; i < first.length; i++) {
            first[i] = -1;
        }
        first[0] = 0;

        int mask = 0;
        int answer = 0;
        for (int i = 0; i < s.length(); i++) {
            int d = s.charAt(i) - '0';
            mask ^= 1 << d;

            if (first[mask] != -1) {
                answer = Math.max(answer, (i + 1) - first[mask]);
            } else {
                first[mask] = i + 1;
            }

            for (int k = 0; k < 10; k++) {
                int m2 = mask ^ (1 << k);
                if (first[m2] != -1) {
                    answer = Math.max(answer, (i + 1) - first[m2]);
                }
            }
        }

        return answer;
    }
}

// 两个前缀掩码相同表示区间内所有数字出现次数均为偶数。
func longestAwesome(s string) int {
	first := make([]int, 1<<10)
	for i := 0; i < len(first); i++ {
		first[i] = -1
	}
	first[0] = 0

	mask := 0
	answer := 0
	for i := 0; i < len(s); i++ {
		d := int(s[i] - '0')
		mask ^= 1 << d

		if first[mask] != -1 {
			if i+1-first[mask] > answer {
				answer = i + 1 - first[mask]
			}
		} else {
			first[mask] = i + 1
		}

		for k := 0; k < 10; k++ {
			m2 := mask ^ (1 << k)
			if first[m2] != -1 {
				if i+1-first[m2] > answer {
					answer = i + 1 - first[m2]
				}
			}
		}
	}
	return answer
}

复杂度分析

时间复杂度：$O(10n)$。字符串扫一遍，每个位置除了一次异或更新外，还要枚举 10 个可翻转的位去查表，每次查表是常数时间的数组随机访问。

空间复杂度：$O(2^{10})$，即常数级。first 数组的长度只由字符集大小 10 决定，与字符串长度无关，其余全是标量。

关键点总结

「重排后能成回文」永远等价于「出现奇数次的字符至多一个」，遇到这句话第一反应就应该是丢掉计数、只留奇偶。

字符集小是压位的信号：$k$ 种字符对应 $2^k$ 种奇偶状态，$k \le 20$ 左右都可以直接用定长数组当哈希表，查询变成 $O(1)$ 的数组访问。

子串的状态等于两个前缀状态的异或，这条恒等式把「枚举 $O(n^2)$ 个子串」压成「对每个右端点查有限个左端点」，是所有前缀异或类题目的公共骨架。

求最长就只记录每个状态的首次出现位置，求计数才需要累加出现次数——这两类需求对哈希表的用法完全不同，不能混。

合法目标状态是有限的 11 种，所以可以正向枚举而不必反向搜索；一旦字符集扩大到 26 个，枚举成本变成 27 倍，思路依旧成立但常数需要重新评估。

面试视角：答题时先把「回文重排 ⟺ 奇数次字符至多一个」和「子串状态 = 前缀状态异或」两句话摆出来，$O(n^2)$ 到 $O(10n)$ 的跨越就完成了，编码只是填空。常见追问是「为什么只记首次出现」，回答要落在「同一状态下左端点越靠左区间越长，后来者严格劣于先到者」，而不是含糊地说「省空间」。

易错点总结

错误写法：不初始化 first[0] = 0。用例 s = "22" → 前缀掩码在下标 1 处变回 0，但表里没有空前缀记录，于是把位置 2 写进 first[0]，返回 1，正确答案是 2。

错误写法：first 数组用 0 而不是 -1 表示「未出现」。用例 s = "213" → 所有未出现的掩码都被误认为在位置 0 出现过，答案被撑到 3，正确答案是 1。

错误写法：查到已存在的 mask 后仍然覆盖 first[mask] 为当前位置。用例 s = "1111" 的掩码 0 在前缀位置 0、2、4 重复出现；若不断覆盖最早位置，最终只能得到长度 2，正确答案是 4。

错误写法：只比较掩码相同的情况，不枚举翻转一位。用例 s = "32424" 中最长全偶子串长度为 4，但整个串只有数字 3 出现奇数次，可以重排成回文，正确答案是 5。

错误写法：在枚举 m2 时也把尚未出现的 first[m2] 写成当前位置。用例 s = "210" 会伪造并不存在的前缀状态，错误得到长度 2；三个数字都只出现一次，正确答案是 1。

错误写法：区间长度写成 i - first[mask] 而不是 (i + 1) - first[mask]。用例 s = "11" → 答案少 1 变成 1，正确答案是 2。

错误写法：用 mask |= 1 << d 而不是异或。用例 s = "11" → 掩码只增不减，第二个 1 没能把标志位翻回去，返回 1，正确答案是 2。

错误写法：把「可重排成回文」错读成「本身是回文」。用例 s = "3242415" → 只找真回文子串得到 "242" 长度 3，正确答案是 5，对应 "32424"。

错误写法：认为奇数次的字符必须恰好有一个，把「全偶」的情况排除掉。用例 s = "1221" → 全偶区间被跳过，返回 3，正确答案是 4。

相似题目

题目	难度	考察点
1177. 构建回文串检测	中等	区间是给定的，改为离线前缀异或后按查询回答，还允许替换 k 次
409. 最长回文串	简单	对象是整个字符集而非子串，直接统计成对字符加一个落单字符
面试题 01.04. 回文排列	简单	只判断整串能否重排成回文，是本题判定条件的最小形态
525. 连续数组	中等	同样是记首次出现求最长，但状态是单个计数差而不是位掩码
1310. 子数组异或查询	中等	前缀异或的直接应用，求的是区间异或值本身而非状态配对
1442. 形成两个异或相等数组的三元组数目	中等	由异或相等推出三元组计数，重点在同值前缀的组合数
318. 最大单词长度乘积	中等	同样把 26 个字母压成位掩码，判定条件换成两掩码按位与为零