AdditionalFile4970.zip

P3590 [POI 2015 R2] 三座塔 Three towers

题目描述

给定一个长度为 $n$ 的仅包含 $\texttt B$、$\texttt C$、$\texttt S$ 三种字符的字符串，请找到最长的一段连续子串，使得这一段要么只有一种字符，要么有多种字符，但是没有任意两种字符出现次数相同。

输入格式

第一行包含一个正整数 $n$（$1\leq n\leq 10^6$），表示字符串的长度。

第二行一个长度为 $n$ 的字符串。

输出格式

包含一行一个正整数，即最长的满足条件的子串的长度。

输入输出样例 #1

输入 #1

9
CBBSSBCSC

输出 #1

6

说明/提示

【样例解释】

选择 $\texttt {BSSBCS}$ 这个子串。

原题名称：Trzy wieże。

#4970. 「POI2015 R2」三座塔 Three towers

标签: 传统 | 时间限制: 2500 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXII Olimpiada Informatyczna — II etap Trzy Wieże

Bitoni 爱玩积木。他在房间里将 $n$ 块积木排成一列，每块积木是白色、灰色或黑色三种颜色之一。Bitoni 想挑选一段连续的积木，从中搭建塔楼。

每座塔楼只能由单一颜色的积木组成，且不能有两座塔楼颜色相同（因此最多建三座塔）。此外，每座塔楼的高度（即积木数量）必须互不相同。Bitoni 必须用完所有选中的积木。请你帮助Bitoni，编写程序找出满足他要求的最长连续积木段。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 1000000)$，表示积木数量。

第二行包含一个由 $n$ 个字母 $a_1 a_2 \ldots a_n$ 组成的字符串，其中 $a_i$ 为 $\texttt{B}$、$\texttt{S}$ 或 $\texttt{C}$，分别表示第 $i$ 块积木的颜色（$\texttt{B}$ 为白色，$\texttt{S}$ 为灰色，$\texttt{C}$ 为黑色）。

输出格式

输出一行，一个整数，表示满足 Bitoni 要求的最长连续积木段的积木数量。

样例

输入

9
CBBSSBCSC

输出

6

Bitoni 可选择 $6$ 块积木的片段 $\texttt{BSSBCS}$，搭建一座 $3$ 块的灰色塔、一座 $2$ 块的白色塔和一座 $1$ 块的黑色塔。

附加样例

1. $n=2500$，积木序列为 $\texttt{B}^{1248} \texttt{C}\underline{\texttt{SB}^{1250}}$（$\texttt{B}^k$ 表示 $k$ 个 B），最长可选片段已标示；
2. $n=1000000$，积木序列为周期性 $\texttt{BSCBSCBSC}\ldots\texttt{BSC}$，Bitoni 只能用 $1$ 块积木建一座塔。

数据范围与提示

对于 $30\%$ 的数据，$n \leq 2500$。