题目背景

2025 年 03 月 GESP C++ 七级编程第 Y 题

题目描述

给定一个仅包含小写英文字母的字符串 (S)，请找出其中最长的子串，使得该子串中每个字母出现的次数均为偶数。
如果不存在满足条件的非空子串，则输出 0。

例如，对于字符串 "aabbcc"，整个字符串中每个字母均出现偶数次，因此答案为 6；
对于字符串 "aba"，最长满足条件的子串为 "bb"（如果输入为 "abba" 则答案为 4）。

输入格式

• 第一行，一个正整数 \(n\)（\(1 \leq n \leq 2 \times 10^5\)），表示字符串 (S) 的长度。
• 第二行，一个仅包含小写英文字母的字符串 (S)。

输出格式

• 一行，一个整数，表示满足条件的最长子串的长度。

样例

6
aabbcc

6

提示

• 同样使用前缀位掩码技术：定义状态 (P[i]) 为前 (i) 个字符的奇偶性状态。
• 对于任意子串 \(S[i+1 \dots j]\)，若 \(P[j] \oplus P[i] = 0\)（即 \(P[j] = P[i]\)），说明该子串中所有字母出现次数均为偶数。
• 利用状态第一次出现的位置，可以在 \(O(n)\) 内求出最长的满足条件的子串长度。