Optimal Disjoint Palindrome Selection

Hard

You are given a string s consisting of lowercase English letters and a positive integer k representing the minimum allowable length for each selected segment. Your task is to choose a collection of non-overlapping substrings from s such that: Length Requirement : Each chosen substring must have a length of at least k characters. Palindrome Property : Each chosen substring must read the same forwards and backwards (i.e., it must be a palindrome). Disjoint Constraint : No two chosen substrings may share any character positions—they must be completely separate within the original string. A substring is defined as a contiguous sequence of characters within the string—characters that appear consecutively without gaps. A palindrome is a sequence that remains identical when reversed. For example, "aba", "noon", and "racecar" are palindromes, while "abc" and "hello" are not. Your goal is to maximize the count of substrings in your selection. Return the maximum number of non-overlapping palindromic substrings that satisfy all the conditions above.

Example 1

Input

s = "abaccdbbd"
k = 3

Output

Explanation

We can select the palindromic substrings "aba" (positions 0-2) and "dbbd" (positions 5-8). Both substrings are palindromes with length at least 3, and they do not overlap. It can be proven that selecting more than 2 valid substrings is impossible.

Example 2

Input

s = "adbcda"
k = 2

Output

Explanation

Although the string contains individual characters and some patterns, there are no palindromic substrings with length 2 or more. The potential candidates like "ad", "db", "bc", "cd", "da" are all non-palindromic, so the maximum count is 0.

Example 3

Input

s = "abaxyzcdc"
k = 3

Output

Explanation

We can select "aba" (positions 0-2) and "cdc" (positions 6-8). Both are palindromes of length 3, and they are non-overlapping. This achieves the maximum possible count of 2.

Constraints

1 ≤ k ≤ s.length ≤ 2000
s consists only of lowercase English letters ('a' through 'z').