<p>Given a string <code>s</code> and an integer <code>k</code>, partition <code>s</code> into <code>k</code> <strong><span data-keyword="substring-nonempty">substrings</span></strong> such that the letter changes needed to make each substring a <strong>semi-palindrome</strong>&nbsp;are minimized.</p>

<p>Return the <em><strong>minimum</strong> number of letter changes</em> required<em>.</em></p>

<p>A <strong>semi-palindrome</strong> is a special type of string that can be divided into <strong><span data-keyword="palindrome">palindromes</span></strong> based on a repeating pattern. To check if a string is a semi-palindrome:​</p>

<ol>
	<li>Choose a positive divisor <code>d</code> of the string&#39;s length. <code>d</code> can range from <code>1</code> up to, but not including, the string&#39;s length. For a string of length <code>1</code>, it does not have a valid divisor as per this definition, since the only divisor is its length, which is not allowed.</li>
	<li>For a given divisor <code>d</code>, divide the string into groups where each group contains characters from the string that follow a repeating pattern of length <code>d</code>. Specifically, the first group consists of characters at positions <code>1</code>, <code>1 + d</code>, <code>1 + 2d</code>, and so on; the second group includes characters at positions <code>2</code>, <code>2 + d</code>, <code>2 + 2d</code>, etc.</li>
	<li>The string is considered a semi-palindrome if each of these groups forms a palindrome.</li>
</ol>

<p>Consider the string <code>&quot;abcabc&quot;</code>:</p>

<ul>
	<li>The length of <code>&quot;abcabc&quot;</code> is <code>6</code>. Valid divisors are <code>1</code>, <code>2</code>, and <code>3</code>.</li>
	<li>For <code>d = 1</code>: The entire string <code>&quot;abcabc&quot;</code> forms one group. Not a palindrome.</li>
	<li>For <code>d = 2</code>:
	<ul>
		<li>Group 1 (positions <code>1, 3, 5</code>): <code>&quot;acb&quot;</code></li>
		<li>Group 2 (positions <code>2, 4, 6</code>): <code>&quot;bac&quot;</code></li>
		<li>Neither group forms a palindrome.</li>
	</ul>
	</li>
	<li>For <code>d = 3</code>:
	<ul>
		<li>Group 1 (positions <code>1, 4</code>): <code>&quot;aa&quot;</code></li>
		<li>Group 2 (positions <code>2, 5</code>): <code>&quot;bb&quot;</code></li>
		<li>Group 3 (positions <code>3, 6</code>): <code>&quot;cc&quot;</code></li>
		<li>All groups form palindromes. Therefore, <code>&quot;abcabc&quot;</code> is a semi-palindrome.</li>
	</ul>
	</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1: </strong></p>

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> s = &quot;abcac&quot;, k = 2 </span></p>

<p><strong>Output: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> 1 </span></p>

<p><strong>Explanation: </strong> Divide <code>s</code> into <code>&quot;ab&quot;</code> and <code>&quot;cac&quot;</code>. <code>&quot;cac&quot;</code> is already semi-palindrome. Change <code>&quot;ab&quot;</code> to <code>&quot;aa&quot;</code>, it becomes semi-palindrome with <code>d = 1</code>.</p>
</div>

<p><strong class="example">Example 2: </strong></p>

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> s = &quot;abcdef&quot;, k = 2 </span></p>

<p><strong>Output: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> 2 </span></p>

<p><strong>Explanation: </strong> Divide <code>s</code> into substrings <code>&quot;abc&quot;</code> and <code>&quot;def&quot;</code>. Each&nbsp;needs one change to become semi-palindrome.</p>
</div>

<p><strong class="example">Example 3: </strong></p>

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> s = &quot;aabbaa&quot;, k = 3 </span></p>

<p><strong>Output: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> 0 </span></p>

<p><strong>Explanation: </strong> Divide <code>s</code> into substrings <code>&quot;aa&quot;</code>, <code>&quot;bb&quot;</code> and <code>&quot;aa&quot;</code>.&nbsp;All are already semi-palindromes.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= s.length &lt;= 200</code></li>
	<li><code>1 &lt;= k &lt;= s.length / 2</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
</ul>

class Solution:
    def minimumChanges(self, s: str, k: int) -> int:
        #print()
        n = len(s)
        # A string of length len is considered a d-semi-palindrome
        # if and only if d is a proper divisor of len and all the
        # subsequences formed by taking the characters of the string
        # whose indices have the same modulo by d are palindromes.

        # We construct sp_arr such that for integer 0 <= i2 < n,
        # integer 0 <= length_minus_2 < i2:
        #  sp_arr[i2][length_minus_2] is the smallest number of letter
        # changes to turn the substring of s ending at index i2 of
        # length (length_minus_2 + 2) into a semi-palindrome.
        # Note that by the definition of a semi-palindrome, there are
        # no semi-palindromes of length less than 2, which justifies the
        # omission of these lengths from sp_arr
        sp_arr = [[float("inf")] * i2 for i2 in range(1, n)]
        for d in range(1, (n >> 1) + 1):
            # For the current d-value, we construct d_sp_arr such that
            # for integer (2 * d - 1) <= i2 < n, and integer
            # 2 <= p_l <= n // d:
            #  d_sp_arr[i2 - 2 * d + 1][p_l - 2] is the smallest number
            # of letter changes to turn the substring of s ending at index
            # i2 of length (p_l * d) into a d-semi-palindrome.
            # The parameter p_l is used rather than length_minus_2 due
            # to the lengths considered being multiples of d. p_l represents
            # the number of letters in each palindrome of the substring
            # (i.e. the number of characters whose index is the same modulo
            # d in the considered substring)
            displ = (d << 1) - 1
            d_sp_arr = [[float("inf")] * (((i2 + 1) // d) - 1) for i2 in range(displ, n)]
            # Strings with corresponding palindromes for this d-value
            # of lengths 2 and 3
            mx_p_l = n // d + 1
            for p_l in range(2, min(4, mx_p_l)):
                length_minus_1 = p_l * d - 1
                for i2 in range(length_minus_1, n):
                    i1 = i2 - length_minus_1
                    ans = sum(s[i1 + j] != s[i2 - d + j + 1] for j in range(d))
                    d_sp_arr[i2 - displ][p_l - 2] = ans
                    sp_arr[i2 - 1][length_minus_1 - 1] = min(sp_arr[i2 - 1][length_minus_1 - 1], ans)
            for p_l in range(4, mx_p_l):
                length_minus_1 = p_l * d - 1
                for i2 in range(length_minus_1, n):
                    i1 = i2 - length_minus_1
                    ans = d_sp_arr[i2 - d - displ][p_l - 4] +\
                            sum(s[i1 + j] != s[i2 - d + j + 1] for j in range(d))
                    d_sp_arr[i2 - displ][p_l - 2] = ans
                    sp_arr[i2 - 1][length_minus_1 - 1] = min(sp_arr[i2 - 1][length_minus_1 - 1], ans)

        # Finally, we use sp_arr and bottom-up 1D dynamic programming to find,
        # for each integer 0 <= j < k in ascending order and the relevant
        # integers 0 <= i2 < n, the minimum number of letter changes needed
        # to make the substring s[0:i2 + 1] able to be partitioned into
        # (j + 1) semi-palindromes.
        # The returned value is then the value calculated for when j = k - 1 and
        # i2 = n - 1

        # We use the observation that a semi-palindrome must have length
        # at least 2 to reduce the number of calculations performed and
        # space used.
        # Specifically, in the jth iteration the values when 0 <= i2 < (2 * j + 1)
        # and when (n - 2 * (k - j) - 1) <= i2 < k are not needed for
        # the calculation of the returned value (either directly or
        # indirectly), and so are omitted from the 1d DP array curr.
        # This results in index i2_displ of the array curr for iteration
        # j corresponding to i2 - 2 * j - 1
        arr_len = n - (k << 1) + 1
        curr = [sp_arr[i2_minus_1][i2_minus_1] for i2_minus_1 in range(arr_len)]
        for j in range(1, k):
            prev = curr
            curr = [float("inf")] * arr_len
            j2 = j << 1
            for i2 in range(j2 + 1, n - ((k - j - 1) << 1)):
                i2_displ = i2 - j2 - 1
                for length_minus_1 in range(1, i2_displ + 2):
                    curr[i2_displ] = min(curr[i2_displ], prev[i2_displ - length_minus_1 + 1]\
                            + sp_arr[i2 - 1][length_minus_1 - 1])
        return curr[-1]
1141