Hard

题目描述

给你一个字符串 s。一个精彩子串是 s 的一个非空子串，我们可以通过任意次数的交换操作使其变成回文串。

返回 s 中最长精彩子串的长度。

示例 1：

输入：s = "3242415"
输出：5
解释："24241" 是最长精彩子串，我们可以通过一些交换操作形成回文串 "24142"。

示例 2：

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

示例 3：

输入：s = "213123"
输出：6
解释："213123" 是最长精彩子串，我们可以通过一些交换操作形成回文串 "231132"。

提示：

  • 1 <= s.length <= 10^5
  • s 只包含数字字符

提示：

  • 给定字符计数，在什么条件下可以形成回文串？
  • 从左到右，使用位异或运算计算任意前缀中每个数字出现次数的奇偶性。
  • 期望复杂度是 O(n*A)，其中 A 是字母表大小（10）。

解题思路

这道题需要理解两个关键点：

  1. 回文串的性质：一个字符串可以重排成回文串当且仅当最多有一个字符的出现次数为奇数。

  2. 状态压缩技巧：由于只有10个数字（0-9），我们可以用一个10位的二进制数来表示每个数字的奇偶性状态。第i位为1表示数字i出现奇数次，为0表示偶数次。

核心思路：

  • 使用前缀异或的方法，维护从字符串开始到当前位置的状态掩码
  • 对于区间[i,j]，如果mask[j] ^ mask[i-1]的结果最多只有1个bit为1，那么这个区间就是精彩子串
  • 这意味着我们需要找到两个位置的掩码，它们的异或结果为0（完全相同）或只有1个bit不同

实现策略：

  • 遍历字符串，维护当前的状态掩码
  • 对于每个位置，检查之前是否存在掩码值相同的位置（异或为0）
  • 检查之前是否存在只有1个bit不同的掩码（异或结果只有1个bit为1）
  • 使用哈希表记录每个掩码第一次出现的位置，以最大化子串长度

代码实现

class Solution {
public:
    int longestAwesome(string s) {
        int n = s.length();
        vector<int> pos(1024, -1);  // 记录每个掩码第一次出现的位置
        pos[0] = 0;  // 初始状态，空字符串的掩码为0
        
        int mask = 0;
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            mask ^= 1 << (s[i] - '0');  // 更新当前掩码
            
            // 情况1：找到相同的掩码（异或为0，偶数个奇数字符）
            if (pos[mask] != -1) {
                maxLen = max(maxLen, i + 1 - pos[mask]);
            } else {
                pos[mask] = i + 1;
            }
            
            // 情况2：找到只差一个bit的掩码（异或为2的幂，一个奇数字符）
            for (int j = 0; j < 10; j++) {
                int target = mask ^ (1 << j);
                if (pos[target] != -1) {
                    maxLen = max(maxLen, i + 1 - pos[target]);
                }
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        pos = [-1] * 1024  # 记录每个掩码第一次出现的位置
        pos[0] = 0  # 初始状态
        
        mask = 0
        max_len = 0
        
        for i in range(n):
            mask ^= 1 << int(s[i])  # 更新当前掩码
            
            # 情况1：找到相同的掩码
            if pos[mask] != -1:
                max_len = max(max_len, i + 1 - pos[mask])
            else:
                pos[mask] = i + 1
            
            # 情况2：找到只差一个bit的掩码
            for j in range(10):
                target = mask ^ (1 << j)
                if pos[target] != -1:
                    max_len = max(max_len, i + 1 - pos[target])
        
        return max_len

public class Solution {
    public int LongestAwesome(string s) {
        int n = s.Length;
        int[] pos = new int[1024];
        Array.Fill(pos, -1);
        pos[0] = 0;
        
        int mask = 0;
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            mask ^= 1 << (s[i] - '0');
            
            if (pos[mask] != -1) {
                maxLen = Math.Max(maxLen, i + 1 - pos[mask]);
            } else {
                pos[mask] = i + 1;
            }
            
            for (int j = 0; j < 10; j++) {
                int target = mask ^ (1 << j);
                if (pos[target] != -1) {
                    maxLen = Math.Max(maxLen, i + 1 - pos[target]);
                }
            }
        }
        
        return maxLen;
    }
}

var longestAwesome = function(s) {
    const n = s.length;
    const pos = new Array(1024).fill(-1);
    pos[0] = 0;
    
    let mask = 0;
    let maxLen = 0;
    
    for (let i = 0; i < n; i++) {
        mask ^= 1 << parseInt(s[i]);
        
        if (pos[mask] !== -1) {
            maxLen = Math.max(maxLen, i + 1 - pos[mask]);
        } else {
            pos[mask] = i + 1;
        }
        
        for (let j = 0; j < 10; j++) {
            const target = mask ^ (1 << j);
            if (pos[target] !== -1) {
                maxLen = Math.max(maxLen, i + 1 - pos[target]);
            }
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n × A)，其中 n 是字符串长度，A = 10 是数字字符的数量
空间复杂度O(2^A) = O(1024) = O(1)，用于存储所有可能的掩码状态