← 返回题目列表

Codeforces · 909/D

D. 多彩点

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

给你一组直线上的点。每个点都分配有一种颜色。对于点 a,它的邻居是与 a 之间没有任何其他点的点。每个点至多有两个邻居 - 一个来自左侧,一个来自右侧。

您对这组点执行一系列操作。在一项操作中,您可以删除具有与该点本身颜色不同的相邻点的所有点。点是同时删除的,即首先您决定必须删除哪些点,然后删除它们。之后您可以执行下一个操作等。如果操作不会删除任何点,则无法执行它。

您需要执行多少次操作,直到下一个操作没有任何要删除的点?

输入

输入包含一个由小写英文字母“a”-“z”组成的字符串。这些字母按照点在线上排列的顺序给出点的颜色:第一个字母给出最左边点的颜色,第二个字母给出左边第二个点的颜色,等等。

点数在 1 到 106 之间。

输出

输出一行包含一个整数 - 可以对给定的一组点执行的操作数,直到没有更多的点可以删除。

示例

输入 #1

aabb

输出 #1

2

输入 #2

aabcaa

输出 #2

1

注意

在第一个测试用例中,第一个操作将删除两个中间点并留下点“ab”,第二个操作将删除该点。将没有剩余点可以应用第三次操作。

在第二个测试用例中,第一个操作将删除中间的四个点,留下点“aa”。它们都没有其他颜色的邻居,因此无法应用第二个操作。