2911

2911. Minimum Changes to Make K Semi-palindromes (Hard)

Given a string s and an integer k, partition s into k substrings such that the sum of the number of letter changes required to turn each substring into a semi-palindrome is minimized.

Return an integer denoting the minimum number of letter changes required.

Notes

• A string is a palindrome if it can be read the same way from left to right and right to left.
• A string with a length of len is considered a semi-palindrome if there exists a positive integer d such that 1 <= d < len and len % d == 0, and if we take indices that have the same modulo by d, they form a palindrome. For example, "aa", "aba", "adbgad", and, "abab" are semi-palindrome and "a", "ab", and, "abca" are not.
• A substring is a contiguous sequence of characters within a string.

 

Example 1:

Input: s = "abcac", k = 2
Output: 1
Explanation: We can divide s into substrings "ab" and "cac". The string "cac" is already a semi-palindrome. If we change "ab" to "aa", it becomes a semi-palindrome with d = 1.
It can be shown that there is no way to divide the string "abcac" into two semi-palindrome substrings. Therefore, the answer would be at least 1.

Example 2:

Input: s = "abcdef", k = 2
Output: 2
Explanation: We can divide it into substrings "abc" and "def". Each of the substrings "abc" and "def" requires one change to become a semi-palindrome, so we need 2 changes in total to make all substrings semi-palindrome.
It can be shown that we cannot divide the given string into two substrings in a way that it would require less than 2 changes.

Example 3:

Input: s = "aabbaa", k = 3
Output: 0
Explanation: We can divide it into substrings "aa", "bb" and "aa".
The strings "aa" and "bb" are already semi-palindromes. Thus, the answer is zero.

 

Constraints:

• 2 <= s.length <= 200
• 1 <= k <= s.length / 2
• s consists only of lowercase English letters.

Related Topics:
Two Pointers, String, Dynamic Programming

Similar Questions:

• Palindrome Partitioning III (Hard)

Hints:

• Define dp[i][j] as the minimum count of letter changes needed to split the suffix of string s starting from s[i] into j valid parts.
• We have dp[i][j] = min(dp[x + 1][j - 1] + v[i][x]). Here v[i][x] is the minimum number of letter changes to change substring s[i..x] into semi-palindrome.
• v[i][j] can be calculated separately by brute-force. We can create a table of v[i][j] independently to improve the complexity. Also note that semi-palindrome’s length is at least 2.

Solution 1.

Let dp[k][i+1] be the min changes needed to change A[0..i] to k substrings that are semi-palindromes (1 <= k <= i+1). The answer is dp[K][N].

dp[0][0] = 0
dp[k][i+1] = min(dp[k-1][j] + c[j][i] | k-1 <= j <= i)

Where c[i][j] is the min changes needed to make A[i..j] semi-palindrome.

We precompute all c[i][j] values. Each c[i][j] computation takes O(N^2) time. So computing all c[i][j] values takes O(N^4).

The DP computation part takes O(N^2 * K) time.

// OJ: https://leetcode.com/problems/minimum-changes-to-make-k-semi-palindromes
// Author: github.com/lzl124631x
// Time: O(N^4 + N^2 * K)
// Space: O(N^2 + NK)
class Solution {
public:
    int minimumChanges(string s, int K) {
        int N = s.size();
        vector<vector<int>> c(N, vector<int>(N, INT_MAX)), dp(K + 1, vector<int>(N + 1, INT_MAX));
        auto minChanges = [&](int from, int to) {
            int ans = INT_MAX, len = to - from + 1;
            for (int d = 1; d < len; ++d) {
                if (len % d) continue;
                int cnt = 0;
                for (int offset = 0; offset < d; ++offset) {
                    string tmp;
                    for (int i = from + offset; i <= to; i += d) tmp += s[i];
                    int i = 0, j = tmp.size() - 1;
                    while (i < j) {
                        cnt += tmp[i++] != tmp[j--];
                    }
                }
                ans = min(ans, cnt);
            }
            return ans;
        };
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                c[i][j] = minChanges(i, j);
            }
        }
        dp[0][0] = 0;
        for (int k = 1; k <= K; ++k) {
            for (int i = 0; i < N; ++i) {
                for (int j = k - 1; j < i; ++j) {
                    if (dp[k - 1][j] != INT_MAX) dp[k][i + 1] = min(dp[k][i + 1], dp[k - 1][j] + c[j][i]);
                }
            }
        }
        return dp[K][N];
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/minimum-changes-to-make-k-semi-palindromes
// Author: github.com/lzl124631x
// Time: O(N^4 + N^2 * K)
// Space: O(N^2 + NK)
class Solution {
public:
    int minimumChanges(string s, int K) {
        int N = s.size();
        vector<vector<int>> memo(N, vector<int>(K + 1, -1)), ops(N, vector<int>(N, -1));
        auto minStringChanges = [&](int start, int end) {
            if (ops[start][end] != -1) return ops[start][end];
            int len = end - start + 1, ans = len;
            for (int d = len - 1; d >= 1; d--) {
                if (len % d != 0) continue;
                int cnt = 0;
                for (int i = 0; i < d; i++) {
                    int left = start + i, right = (start + i) + (end - start - i) / d * d;
                    while (left < right) {
                        if (s[left] != s[right]) cnt++;
                        left += d;
                        right -= d;
                    }
                }
                ans = min(ans, cnt);
            }
            return ops[start][end] = ans;
        };
        function<int(int, int)> minChanges = [&](int idx, int residual) {
            if (memo[idx][residual] != -1) return memo[idx][residual];
            if (residual == 1) return minStringChanges(idx, N - 1);
            int ans = INT_MAX;
            for (int i = idx + 1; i + (residual - 1) * 2 < N; i++) {
                ans = min(ans, minStringChanges(idx, i) + minChanges(i + 1, residual - 1));
            }
            return memo[idx][residual] = ans;
        };
        return minChanges(0, K);
    }
};