Problem

Given a string s and an integer k, partition s into k 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 palindromes based on a repeating pattern. To check if a string is a semi-palindrome:​

  1. 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.
  2. 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.
  3. 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.

Examples

Example 1

1
2
3
4
5
6
7


Input: s = "abcac", k = 2

Output: 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

1
2
3
4
5
6
7


Input: s = "abcdef", k = 2

Output: 2

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

Example 3

1
2
3
4
5
6
7


Input: s = "aabbaa", k = 3

Output: 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.

Solution

Method 1 – Dynamic Programming + Semi-palindrome Cost Precomputation

Intuition

To minimize changes, we need to split the string into k substrings and, for each, find the minimum changes to make it a semi-palindrome. Precompute the cost for every substring to become a semi-palindrome, then use dynamic programming to find the optimal partitioning.

Approach

  1. For every substring, precompute the minimum changes needed to make it a semi-palindrome:
    • For each possible divisor d, group characters and count changes to make each group a palindrome.
    • Take the minimum over all valid divisors.
  2. Use DP: dp[i][j] = min changes to partition first i characters into j semi-palindromes.
    • For each partition, try all possible previous cuts and update dp.
  3. Return dp[n][k] where n is the length of s.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
public:
    int minChanges(string s, int k) {
        int n = s.size();
        vector<vector<int>> cost(n, vector<int>(n, 0));
        for (int l = 0; l < n; ++l) {
            for (int r = l; r < n; ++r) {
                int len = r - l + 1, minCost = INT_MAX;
                for (int d = 1; d < len; ++d) {
                    if (len % d != 0) continue;
                    int cur = 0;
                    for (int i = 0; i < d; ++i) {
                        int left = i, right = len - d + i;
                        while (left < right) {
                            if (s[l + left] != s[l + right]) cur++;
                            left += d;
                            right -= d;
                        }
                    }
                    minCost = min(minCost, cur);
                }
                cost[l][r] = (len == 1 ? 0 : minCost);
            }
        }
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                for (int p = j - 1; p < i; ++p) {
                    if (dp[p][j - 1] != INT_MAX && cost[p][i - 1] != INT_MAX)
                        dp[i][j] = min(dp[i][j], dp[p][j - 1] + cost[p][i - 1]);
                }
            }
        }
        return dp[n][k];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

func minChanges(s string, k int) int {
    n := len(s)
    cost := make([][]int, n)
    for i := range cost {
        cost[i] = make([]int, n)
    }
    for l := 0; l < n; l++ {
        for r := l; r < n; r++ {
            len := r - l + 1
            minCost := 1 << 30
            for d := 1; d < len; d++ {
                if len%d != 0 {
                    continue
                }
                cur := 0
                for i := 0; i < d; i++ {
                    left, right := i, len-d+i
                    for left < right {
                        if s[l+left] != s[l+right] {
                            cur++
                        }
                        left += d
                        right -= d
                    }
                }
                if cur < minCost {
                    minCost = cur
                }
            }
            if len == 1 {
                cost[l][r] = 0
            } else {
                cost[l][r] = minCost
            }
        }
    }
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, k+1)
        for j := range dp[i] {
            dp[i][j] = 1 << 30
        }
    }
    dp[0][0] = 0
    for i := 1; i <= n; i++ {
        for j := 1; j <= k; j++ {
            for p := j - 1; p < i; p++ {
                if dp[p][j-1] < 1<<30 && cost[p][i-1] < 1<<30 {
                    if dp[p][j-1]+cost[p][i-1] < dp[i][j] {
                        dp[i][j] = dp[p][j-1] + cost[p][i-1]
                    }
                }
            }
        }
    }
    return dp[n][k]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public int minChanges(String s, int k) {
        int n = s.length();
        int[][] cost = new int[n][n];
        for (int l = 0; l < n; ++l) {
            for (int r = l; r < n; ++r) {
                int len = r - l + 1, minCost = Integer.MAX_VALUE;
                for (int d = 1; d < len; ++d) {
                    if (len % d != 0) continue;
                    int cur = 0;
                    for (int i = 0; i < d; ++i) {
                        int left = i, right = len - d + i;
                        while (left < right) {
                            if (s.charAt(l + left) != s.charAt(l + right)) cur++;
                            left += d;
                            right -= d;
                        }
                    }
                    minCost = Math.min(minCost, cur);
                }
                cost[l][r] = (len == 1 ? 0 : minCost);
            }
        }
        int[][] dp = new int[n + 1][k + 1];
        for (int[] arr : dp) Arrays.fill(arr, Integer.MAX_VALUE);
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                for (int p = j - 1; p < i; ++p) {
                    if (dp[p][j - 1] != Integer.MAX_VALUE && cost[p][i - 1] != Integer.MAX_VALUE)
                        dp[i][j] = Math.min(dp[i][j], dp[p][j - 1] + cost[p][i - 1]);
                }
            }
        }
        return dp[n][k];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    fun minChanges(s: String, k: Int): Int {
        val n = s.length
        val cost = Array(n) { IntArray(n) }
        for (l in 0 until n) {
            for (r in l until n) {
                val len = r - l + 1
                var minCost = Int.MAX_VALUE
                for (d in 1 until len) {
                    if (len % d != 0) continue
                    var cur = 0
                    for (i in 0 until d) {
                        var left = i
                        var right = len - d + i
                        while (left < right) {
                            if (s[l + left] != s[l + right]) cur++
                            left += d
                            right -= d
                        }
                    }
                    minCost = minOf(minCost, cur)
                }
                cost[l][r] = if (len == 1) 0 else minCost
            }
        }
        val dp = Array(n + 1) { IntArray(k + 1) { Int.MAX_VALUE } }
        dp[0][0] = 0
        for (i in 1..n) {
            for (j in 1..k) {
                for (p in j - 1 until i) {
                    if (dp[p][j - 1] != Int.MAX_VALUE && cost[p][i - 1] != Int.MAX_VALUE)
                        dp[i][j] = minOf(dp[i][j], dp[p][j - 1] + cost[p][i - 1])
                }
            }
        }
        return dp[n][k]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def min_changes(s: str, k: int) -> int:
    n = len(s)
    cost = [[0] * n for _ in range(n)]
    for l in range(n):
        for r in range(l, n):
            length = r - l + 1
            min_cost = float('inf')
            for d in range(1, length):
                if length % d != 0:
                    continue
                cur = 0
                for i in range(d):
                    left, right = i, length - d + i
                    while left < right:
                        if s[l + left] != s[l + right]:
                            cur += 1
                        left += d
                        right -= d
                min_cost = min(min_cost, cur)
            cost[l][r] = 0 if length == 1 else min_cost
    dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            for p in range(j - 1, i):
                if dp[p][j - 1] != float('inf') and cost[p][i - 1] != float('inf'):
                    dp[i][j] = min(dp[i][j], dp[p][j - 1] + cost[p][i - 1])
    return dp[n][k]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

impl Solution {
    pub fn min_changes(s: String, k: i32) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut cost = vec![vec![0; n]; n];
        for l in 0..n {
            for r in l..n {
                let len = r - l + 1;
                let mut min_cost = i32::MAX;
                for d in 1..len {
                    if len % d != 0 { continue; }
                    let mut cur = 0;
                    for i in 0..d {
                        let mut left = i;
                        let mut right = len - d + i;
                        while left < right {
                            if s[l + left] != s[l + right] { cur += 1; }
                            left += d;
                            right -= d;
                        }
                    }
                    min_cost = min_cost.min(cur);
                }
                cost[l][r] = if len == 1 { 0 } else { min_cost };
            }
        }
        let mut dp = vec![vec![i32::MAX; (k + 1) as usize]; n + 1];
        dp[0][0] = 0;
        for i in 1..=n {
            for j in 1..=k as usize {
                for p in j - 1..i {
                    if dp[p][j - 1] != i32::MAX && cost[p][i - 1] != i32::MAX {
                        dp[i][j] = dp[i][j].min(dp[p][j - 1] + cost[p][i - 1]);
                    }
                }
            }
        }
        dp[n][k as usize]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    minChanges(s: string, k: number): number {
        const n = s.length;
        const cost: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
        for (let l = 0; l < n; l++) {
            for (let r = l; r < n; r++) {
                const len = r - l + 1;
                let minCost = Infinity;
                for (let d = 1; d < len; d++) {
                    if (len % d !== 0) continue;
                    let cur = 0;
                    for (let i = 0; i < d; i++) {
                        let left = i, right = len - d + i;
                        while (left < right) {
                            if (s[l + left] !== s[l + right]) cur++;
                            left += d;
                            right -= d;
                        }
                    }
                    minCost = Math.min(minCost, cur);
                }
                cost[l][r] = len === 1 ? 0 : minCost;
            }
        }
        const dp: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(Infinity));
        dp[0][0] = 0;
        for (let i = 1; i <= n; i++) {
            for (let j = 1; j <= k; j++) {
                for (let p = j - 1; p < i; p++) {
                    if (dp[p][j - 1] !== Infinity && cost[p][i - 1] !== Infinity) {
                        dp[i][j] = Math.min(dp[i][j], dp[p][j - 1] + cost[p][i - 1]);
                    }
                }
            }
        }
        return dp[n][k];
    }
}

Complexity

  • ⏰ Time complexity: O(n^3), due to precomputing costs for all substrings and divisors, and DP partitioning.
  • 🧺 Space complexity: O(n^2), for cost and DP tables.