咨询：寻找每个字符出现偶数次的最长子串长度的解决方案

嘿，这个问题我之前也纠结过，滑动窗口确实不太好直接落地——毕竟这个问题的条件是所有字符出现次数都是偶数，没法像常规滑动窗口那样用简单的收缩条件动态维护窗口合法性。不过我们可以换个经典思路：状态压缩+排序，刚好能满足你要求的最坏O(nlgn)时间复杂度和O(n)空间复杂度！

核心思路：用二进制状态压缩表示奇偶性 #

我们可以用一个整数mask来记录当前遍历位置的字符奇偶状态：

• 假设字符串是小写字母，用26个二进制位对应26个字母，某一位为1表示对应字符出现奇数次，为0表示偶数次。
• 遍历字符串时，每遇到一个字符，就把mask中对应的位翻转（用异或操作mask ^= 1 << (c - 'a')实现）。

关键结论：如果两个位置的mask值相同，说明这两个位置之间的子串所有字符出现次数都是偶数——因为从第一个位置到第二个位置，每个字符的出现次数变化是偶数次（异或后回到原状态），自然都是偶数次。

具体实现步骤（满足O(nlgn)时间要求） #

1. 记录所有状态和对应索引：遍历字符串，把每个位置的mask值和对应的索引存成列表，初始时mask=0对应索引-1（空串的状态，符合所有字符出现0次的偶数要求）。
2. 按状态排序：把列表按mask值排序，这样相同状态的索引会被排在一起。
3. 计算最长子串长度：遍历排序后的列表，对每个相同的mask，记录第一次出现的索引和最后一次出现的索引，两者的差值就是该状态下的最长合法子串长度，最后取所有状态中的最大值即可。

示例代码（Python） #

def longest_even_substring(s):
    mask = 0
    # 初始状态：mask=0对应索引-1（空串）
    mask_index_pairs = [(0, -1)]
    
    for idx, char in enumerate(s):
        # 翻转当前字符对应的二进制位
        char_bit = ord(char) - ord('a')
        mask ^= 1 << char_bit
        mask_index_pairs.append((mask, idx))
    
    # 按mask值排序，让相同状态的索引聚在一起
    mask_index_pairs.sort()
    
    max_length = 0
    current_mask = None
    first_index = None
    
    for m, idx in mask_index_pairs:
        if m != current_mask:
            current_mask = m
            first_index = idx
        else:
            # 计算当前索引与第一个同状态索引的差值
            current_length = idx - first_index
            if current_length > max_length:
                max_length = current_length
    
    return max_length

为什么这个方法符合复杂度要求？ #

• 时间复杂度：遍历字符串是O(n)，排序步骤是O(nlgn)，总时间最坏是O(nlgn)，完全符合你的要求。
• 空间复杂度：存储mask和索引的列表是O(n)，空间控制得很好。

关于你提到的优先队列思路 #

优先队列其实不是最优选择——如果用它存储所有可能的索引对长度，需要先收集所有合法对，空间复杂度会飙升，而且时间效率也不如上面的方法。状态压缩才是这类奇偶次数问题的最优解方向～

内容的提问来源于stack exchange，提问作者Elimination