给你一个字符串 s 和一个整数 k，请将 s 划分为 k 个 非空子串 ，使得将每个子串变为 半回文串 所需的字符修改次数之和最小。

返回所需的 最少 字符修改次数。

半回文串 是一类特殊的字符串：它可以按照某种重复模式拆分后，使每一组都成为 回文串 。判断一个字符串是否为半回文串的方法如下：

1. 选择该字符串长度的一个正因数 d。其中，d 的取值范围是从 1 到严格小于字符串长度的所有正因数。对于长度为 1 的字符串，根据这一定义，它不存在合法的因数，因为唯一的因数就是其长度本身，而这是不允许的。
2. 对于给定的因数 d，将字符串按长度为 d 的重复模式分组。具体来说，第 1 组由位置 1、1 + d、1 + 2d、…… 上的字符组成；第 2 组由位置 2、2 + d、2 + 2d、…… 上的字符组成；以此类推。
3. 如果这些分组中的每一组都是回文串，则该字符串被视为半回文串。

以字符串 "abcabc" 为例：

• "abcabc" 的长度为 6。合法的因数有 1、2 和 3。
• 当 d = 1 时：整个字符串 "abcabc" 构成一组。它不是回文串。
• 当 d = 2 时：
  • 第 1 组（位置 1, 3, 5）："acb"
  • 第 2 组（位置 2, 4, 6）："bac"
  • 这两组都不是回文串。
• 当 d = 3 时：
  • 第 1 组（位置 1, 4）："aa"
  • 第 2 组（位置 2, 5）："bb"
  • 第 3 组（位置 3, 6）："cc"
  • 所有分组都是回文串。因此，"abcabc" 是一个半回文串。

 

示例 1：

示例 2：

示例 3：

 

提示：

• 2 <= s.length <= 200
• 1 <= k <= s.length / 2
• s 仅由小写英文字母组成。