2911-minimum-changes-to-make-k-semi-palindromes.adoc

2911. Minimum Changes to Make K Semi-palindromes

{leetcode}/problems/minimum-changes-to-make-k-semi-palindromes/[LeetCode - 2911. Minimum Changes to Make K Semi-palindromes ^]

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

Return the *minimum* number of letter changes required_._

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

• Choose a positive divisor d of the string’s length. d can range from 1 up to, but not including, the string’s length. For a string of length 1, it does not have a valid divisor as per this definition, since the only divisor is its length, which is not allowed.

• For a given divisor d, divide the string into groups where each group contains characters from the string that follow a repeating pattern of length d. Specifically, the first group consists of characters at positions 1, 1 + d, 1 + 2d, and so on; the second group includes characters at positions 2, 2 + d, 2 + 2d, etc.

• The string is considered a semi-palindrome if each of these groups forms a palindrome.

Consider the string "abcabc":

• The length of "abcabc" is 6. Valid divisors are 1, 2, and 3.

• For d = 1: The entire string "abcabc" forms one group. Not a palindrome.

• For d = 2:

• Group 1 (positions 1, 3, 5): "acb"

• Group 2 (positions 2, 4, 6): "bac"

• Neither group forms a palindrome.

• For d = 3:

• Group 1 (positions 1, 4): "aa"

• Group 2 (positions 2, 5): "bb"

• Group 3 (positions 3, 6): "cc"

• All groups form palindromes. Therefore, "abcabc" is a semi-palindrome.

*Example 1: *

<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;"> *Input: * <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> s = "abcac", k = 2

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

*Explanation: * Divide s into "ab" and "cac". "cac" is already semi-palindrome. Change "ab" to "aa", it becomes semi-palindrome with d = 1.

*Example 2: *

<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;"> *Input: * <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> s = "abcdef", k = 2

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

*Explanation: * Divide s into substrings "abc" and "def". Each needs one change to become semi-palindrome.

*Example 3: *

<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;"> *Input: * <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> s = "aabbaa", k = 3

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

*Explanation: * Divide s into substrings "aa", "bb" and "aa". All are already semi-palindromes.

Constraints:

• 2 ⇐ s.length ⇐ 200

• 1 ⇐ k ⇐ s.length / 2

• s contains only lowercase English letters.

思路分析

一刷

link:{sourcedir}/_2911_MinimumChangesToMakeKSemiPalindromes.java[role=include]

参考资料