等值区间

题目描述

给定一个长度为 n 的 01 串 s（下标从 1 开始），串中每个字符都是 '0' 或 '1'。

定义区间 [l, r]（1 ≤ l ≤ r ≤ n）表示 s 的一个连续子串 s[l..r]。区间内 '1' 的个数称为该区间的 1 数，'0' 的个数称为 0 数。

请你找出两个不同的区间（两个区间不能同时拥有完全相同的左右端点，即不能完全重叠；它们可以相交，也可以重叠一部分），使得这两个区间的 1 数相等且 0 数也相等。

由于满足条件的两个区间长度必然相同（区间长度 = 1 数 + 0 数），请你输出这两个区间可能达到的最大长度。如果不存在这样的两个区间，输出 0。

输入格式

第一行一个正整数 n，表示字符串长度。

第二行一个长度为 n 的字符串 s，仅由字符 '0' 和 '1' 组成。

输出格式

输出一行一个整数，表示满足条件的两个区间可能达到的最大长度；若不存在，输出 0。

样例

4
0101

2

2
01

0

5
00100

4

样例解释

• 样例 1：区间 [1,2]="01" 与 [3,4]="01" 的 1 数（1）和 0 数（1）分别相等，长度为 2；而长度为 3 的两个区间 [1,3]="010" 与 [2,4]="101" 的 1 数不相等。答案为 2。
• 样例 2：长度为 1 的两个区间 "0" 与 "1" 的 1 数不相等；长度为 2 的区间只有一个。答案为 0。
• 样例 3：区间 [1,4]="0010" 与 [2,5]="0100" 的 1 数（1）和 0 数（3）分别相等，长度为 4。答案为 4。

数据范围

• 1 ≤ n ≤ 5000

提示

两个区间要同时满足 1 数相等、0 数相等，则它们的长度必然相同（长度 = 1 数 + 0 数）。因此问题等价于：寻找最大的长度 L，使得存在两个起止位置不同的长度为 L 的连续子串，其 1 的个数相同。

用前缀和可以在 O(1) 时间内算出任意区间的 1 数。从大到小枚举长度 L，对每个 L 用哈希集合检查是否存在两个窗口的 1 数相同，找到的第一个可行 L 即为答案。总复杂度 O(n²)，可以轻松通过 n ≤ 5000。