题目描述

给你一个字符串 $s$ 和一个 正 整数 $k$ 。

从字符串 $s$ 中选出一组满足下述条件且 不重叠 的子字符串：

• 每个子字符串的长度 至少 为 $k$ 。
• 每个子字符串是一个 回文串 。

返回最优方案中能选择的子字符串的 最大 数目。

子字符串 是字符串中一个连续的字符序列。

输入格式

第一行一个字符串 $s$

第二行一个正整 $k$

输出格式

一个整数表示答案。

示例 1 ：

abaccdbbd
3

2

解释： 可以选择 s = "abaccdbbd" 中斜体加粗的子字符串。"aba" 和 "dbbd" 都是回文，且长度至少为 k = 3 。

可以证明，无法选出两个以上的有效子字符串。

示例 2 ：

adbcda
2

0

解释： 字符串中不存在长度至少为 2 的回文子字符串。

提示：

• $1 <= k <= s.length <= 2000$
• $s$ 仅由小写英文字母组成

SOURCE

2472. 不重叠回文子字符串的最大数目