Determine the maximum number of valid substrings that can be formed from $s.$

Notes:

A substring is a group of adjacent characters in a string.

A palindrome is a string that reads the same backward as forward.

Example

$s=$ aababaabce

$k=3$

a ababa abce

a aba baab ce

Any valid substring must be $k$ or more characters long. Either $1$ or $2$ non$-$overlapping palindromes can be formed. Return $2,$ the maximum number that can be formed.

Function Description

Complete the function getMaxSubstrings in the editor below.

getMaxSubstrings has the following parameters:

string s: the given string

int $k$ : the minimum length of a valid substring

Returns

int: the maximum number of valid substrings that can be formed

Constraints

$*1|s|{2\mathrm{.}10}^3$

$-1k|s|$