A7219 | $雾港城的符文$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

雾港城的符文是一段只含小写字母的字符串 $s$。如果符文里出现长度至少为 $2$ 的回文子串，就会触发共鸣。 你可以执行若干次删除操作：每次删除 $s$ 中的一个字符。删除后剩余字符保持原有相对顺序，拼成新字符串 $t$。 你的目标是让 $t$ 中不存在任何长度 $\ge 2$ 的回文子串（也就是任意连续子串都不允许是长度 $\ge 2$ 的回文），并且删除次数尽量少。 请输出最少删除多少个字符。

一行一个字符串 $s$（仅包含小写字母）。

输出一个整数，表示最少删除次数。

输入 #1

abac

输出 #1

样例解释 原串中子串 "aba" 是长度为 $3$ 的回文。删除第 $3$ 个字符 'a' 后得到 $t=\texttt{"abc"}$，此时 $t$ 的任意长度为 $2$ 或 $3$ 的连续子串都不是回文，因此不存在长度 $\ge2$ 的回文子串。并且只删 $1$ 个字符已经足够，所以答案为 $1$。 数据范围与测试点 * $1\le n\le200000$，其中 $n=|s|$ 测试点分层（只给编号范围与 $n$ 上界）： 测试点编号$n$ 上界$1\sim4$$n\le20$$5\sim10$$n\le10000$$11\sim20$$n\le200000$

C++ 编辑器

输入

输出