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

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 微软
标签
字符串 哈希表 位运算

题目描述

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

image-20260929085255192

image-20260929085255258

题意分析

在只包含数字字符的字符串中，选择一段连续、非空子串，使它的字符能够通过任意重排形成回文，返回最长长度。

原子串不需要已经是回文，只看重排是否可能；但选取范围必须连续，不能从多个分散位置拼出候选。返回长度即可，不需要构造回文内容。

解法：前缀奇偶位掩码

核心思路

[!blue]

回文中左右对称位置必须放同一种字符，因此除中间位置外，所有字符都应成对。一个多重集合能重排成回文，当且仅当至多一种字符出现奇数次：成对部分分放两侧，唯一的奇数余项放中央，就能构造成功。

数字只有十种，用十位掩码记录前缀中每种数字出现次数的奇偶，一表示奇数、零表示偶数。遇到数字 d 就执行 mask ^= 1 << d，同一种数字每再出现一次都会翻转状态。

两个前缀掩码异或，表示它们之间子串的各数字次数奇偶。想让至多一位为一，历史前缀只能与当前掩码相同，或者恰好相差一个位。所以每个右端只需检查当前掩码及逐一翻转十个位后的十种候选。

用 first[mask] 保存真实出现过该掩码的最早前缀长度。对于相同右端和历史状态，越早的前缀产生越长区间，后来再次出现就不应覆盖。空前缀长度为零、状态为零，提前登记 first[0] = 0。

处理字符下标 i 后，当前前缀长度是 i + 1，与历史长度之差就是候选子串长度。只有当前真实掩码可以在首次出现时登记；翻转一位得到的状态只是查询条件，不能伪装成已出现状态写回。

解题步骤

  1. 创建 1024 个状态的最早位置表，初始化为未出现，登记空前缀。
  2. 从左到右处理数字，异或翻转对应位。
  3. 当前状态以前出现过时，用最早位置更新答案；否则登记当前前缀长度。
  4. 依次翻转十个位，查询已经出现过的相差一位状态并更新长度。
  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+2^{10})$，初始化全部状态，每个字符检查固定的十一种历史状态。
  • 空间复杂度：$O(2^{10})$，保存十位掩码的最早前缀长度。

关键点总结

[!green]

  • 重排回文只取决于各字符次数奇偶，不需要保存准确频次。
  • 前缀异或给出区间奇偶，最多一个奇数等价于掩码最多一个置位。
  • 固定右端时保留最早历史状态，才能使长度最大。
  • 查询候选与登记真实状态必须区分。

易错点总结

[!yellow]

  • 按位或只能置一不能翻回零，同数字出现两次时无法恢复偶数状态，必须使用异或。
  • 只查询同掩码会漏掉恰好一种数字出现奇数次的合法子串。
  • 覆盖已经保存的最早位置，会缩短以后可得到的区间。
  • 把翻转一位的候选也写入表，会制造根本没有出现的历史前缀。
  • 存的是前缀长度，当前应使用 i + 1；不能混入字符下标的长度公式。

相似题目

题目 难度 关联与区别
1177. 构建回文串检测 中等 同样用字符频次奇偶掩码判断能否重排回文，本题保存每种前缀掩码的最早位置来求最长区间。
525. 连续数组 中等 两题都保留每种前缀状态的最早位置以求最长区间；525只匹配相同的0/1数量差，本题使用数码频次奇偶掩码，可匹配相同掩码或仅相差一位的掩码。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/33168697
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！