题目内容
小红拿到一个长度为 n 的字符串,她定义一个字符中的权值为最长连续相同字符串的长度。
题解
题意:
- 原串长度为 n,要求恰好删除 k 个字母,也就是说保留 n−k 个字母,构成新串 T。
- 小红定义“一个字符中的权值”为:在新串 T 中存在一段连续子串,可以分成若干个长度相同的“块”(块长为 L≥1),且所有块均相等,这样重复的个数记为 m。
基本思路:
由于删除字母可以任意进行,问题实质转换为:
在原串中是否存在一个子序列(保留字母顺序不变),能构成某个周期字符串,即形如
xm=xx⋯x