#P4384. [POI2015]Trzy wieże

    ID: 3587 传统题 2000ms 128MiB 尝试: 462 已通过: 104 难度: 7 上传者: 标签>难度分类提高+/省选-排序与序列处理一维前缀和组合数学容斥原理二分答案离散化CF2200鸣谢Claris

[POI2015]Trzy wieże

[POI 2015] Trzy wieże 三座塔

题目描述

Bitoni 将 nn 块积木排成一行,每块是白、灰、黑中的一种。他想选一段连续的积木,用选中的全部积木搭塔。一座塔只能用一种颜色,同一颜色只能搭一座塔。若搭了两座或三座塔,它们的高度必须两两不同。没有选到的颜色不搭塔。

求满足要求的最长连续区间包含多少块积木。

输入格式

第一行一个整数 nn(1≤n≤1061\le n\le10^6)。

第二行一个长度为 nn 的字符串,只含 B、S、C,依次表示白、灰、黑。

输出格式

输出一个整数,表示最多能选多少块积木。

样例 #1

样例输入 #1

9
CBBSSBCSC

样例输出 #1

6

提示

样例可以选 BSSBCS:用 33 块灰色、22 块白色及 11 块黑色积木搭成三座塔。

原赛共 30% 的分值满足 n≤2500n\le2500。原赛还描述了两组公开测试:

  • n=2500n=2500,字符串为 B1248CSB1250\texttt{B}^{1248}\texttt{CS}\texttt{B}^{1250},最长合法段为 SB1250\texttt{SB}^{1250}(幂表示重复)。
  • n=106n=10^6,按 BSC 循环生成,最长合法段只含一块积木。