← 返回题目列表

Codeforces · 391/B

B. 字折叠

中文机器翻译题面 查看原题

解决此问题将获得 5 分。

Manao 发明了一种新的字符串操作,称为折叠。每次折叠发生在一对连续的字母之间,并将字符串的第二部分放在第一部分之上,以相反的方向运行并与折叠的位置对齐。使用此操作,Manao 将字符串转换为比执行的折叠操作多一级的结构。为了清楚起见,请参阅以下示例。

我们将用“|”表示折叠的位置人物。例如,单词“ABRACADABRA”写成“AB|RACA|DAB|RA”表示它被折叠了三次:第一次,在最左边的一对“B”和“R”字母之间;第三次,在最左边的一对“B”和“R”字母之间;第三次,在最左边的一对“B”和“R”字母之间;第二,在“A”和“D”之间;第三,在最右边的一对“B”和“R”字母之间。以下是折叠弦的几个示例:

“ABCD|EFGH|IJ|K”的最后一个示例:

Manao 注意到每条折叠的绳子都可以被视为几堆字母。例如,在前面的示例中,有四堆,从下到上可以读为“AHI”、“BGJK”、“CF”和“DE”。 Manao 想知道他对给定单词使用折叠操作可以构建的最高一堆相同字母是多少。请注意,堆垛不应包含间隙,并且应从底层开始。例如,在上面四个示例中最右边的一个中,没有一个桩被认为是有效的,因为每个桩都有间隙,或者从底部水平以上开始,或者两者都有。

输入

输入将由一行组成,其中包含 n 个字符的单个字符串,其中 1 ≤ n ≤ 1000 并且不包含空格。字符串中的所有字符都将是大写字母。

这个问题没有子问题。正确提交您将获得 5 分。

输出

打印单个整数 - 由给定字符串的折叠操作的有效结果中可以看到的由相同字符组成的最大堆的大小。

示例

输入 #1

ABRACADABRA

输出 #1

3

输入 #2

ABBBCBDB

输出 #2

3

输入 #3

AB

输出 #3

1

注意

考虑第一个例子。 Manao 可以使用折叠“AB|RACAD|ABRA”创建一堆三个“A”,从而产生以下结构:

在第二个示例中,Manao 可以使用以下折叠创建一堆三个“B”:“AB|BB|CBDB”。

Manao 用“ABBBCBDB”创建一堆三个“B”的另一种方法是以下折叠:“AB|B|BCBDB”。

在第三个示例中,没有执行折叠,字符串仅写在一行中。