CF909D Colorful Points

题目描述

给定一组位于一条直线上的点。每个点都有一个颜色。对于点 $a$,它的邻居是指那些在它两侧、与它之间没有其它点的点。每个点最多有两个邻居——分别在左侧和右侧。 你需要对这组点执行一系列操作。在每一次操作中,删除所有有一个邻居且邻居的颜色与自身不同的点。点的删除是同时发生的,也就是说,先判断哪些点要被删除,然后一起删除。随后可以进行下一轮操作,依此类推。如果某一轮没有任何点被删除,则不能再进行操作。 问:你最多能进行多少轮操作,直到无法再删除任何点为止?

输入格式

输入为一个由小写英文字母 'a'-'z' 组成的字符串。字母表示点的颜色,顺序表示点从左到右依次排列的颜色:第一个字母为最左侧点的颜色,第二个为第二个点的颜色,依此类推。 点的数量 $n$ 满足 $1 \leq n \leq 10^6$。

输出格式

输出一个整数,表示可以进行的操作次数,直到无法再删除任何点为止。

说明/提示

在第一个测试用例中,第一次操作会删除中间的两个点,剩下“ab”,第二次操作会将其全部删除。此时已无法进行第三次操作。 在第二个测试用例中,第一次操作会删除中间四个点,剩下“aa”。这两个点之间颜色相同,没有不同颜色的邻居,因此无法再进行操作。 由 ChatGPT 5 翻译