Hard

题目描述

给你一个字符串 s 和一个整数 k，将 s 分割成 k 个子字符串，使得将每个子字符串变成半回文字符串所需的字母变更次数最少。

返回所需的最少字母变更次数。

半回文字符串是一种特殊类型的字符串，可以基于重复模式分割成回文字符串。要检查字符串是否为半回文字符串：

  • 选择字符串长度的一个正除数 d。d 的范围从 1 到字符串长度（不包括字符串长度本身）。对于长度为 1 的字符串，根据此定义没有有效的除数，因为唯一的除数是其长度，这是不允许的。
  • 对于给定的除数 d，将字符串分成若干组，每组包含遵循长度为 d 的重复模式的字符。具体来说，第一组由位置 1, 1+d, 1+2d 等处的字符组成；第二组包含位置 2, 2+d, 2+2d 等处的字符，依此类推。
  • 如果每个组都形成回文字符串，则该字符串被认为是半回文字符串。

示例 1：

输入：s = "abcac", k = 2
输出：1
解释：将 s 分为 "ab" 和 "cac"。"cac" 已经是半回文字符串。将 "ab" 改为 "aa"，它变成 d=1 的半回文字符串。

示例 2：

输入：s = "abcdef", k = 2
输出：2
解释：将 s 分为子字符串 "abc" 和 "def"。每个都需要一次变更才能成为半回文字符串。

示例 3：

输入：s = "aabbaa", k = 3
输出：0
解释：将 s 分为子字符串 "aa"、"bb" 和 "aa"。所有都已经是半回文字符串。

约束条件：

  • 2 <= s.length <= 200
  • 1 <= k <= s.length / 2
  • s 只包含小写英文字母

解题思路

这是一道动态规划问题，需要分两步解决：

第一步：预处理计算子字符串变为半回文的最小代价

  • 对于每个子字符串 s[i:j+1]，计算将其变为半回文字符串的最小变更次数
  • 对于长度为 len 的字符串，枚举其所有除数 d（1 ≤ d < len）
  • 对于每个除数 d，将字符串按模式分组，每组形成一个子序列
  • 计算每个子序列变为回文所需的变更次数，取所有除数中的最小值

第二步：动态规划求解分割问题

  • 定义 dp[i][j] 表示将 s[i:] 分割成 j 部分的最小变更次数
  • 状态转移：dp[i][j] = min(dp[x+1][j-1] + cost[i][x]) 对所有有效的 x
  • 其中 cost[i][x] 是将 s[i:x+1] 变为半回文的最小代价
  • 边界条件：dp[n][0] = 0，其他初始化为无穷大

时间复杂度分析：

  • 预处理：O(n³ × d(n))，其中 d(n) 是除数个数
  • DP：O(n² × k)
  • 总体：O(n³ × d(n) + n² × k)

由于 n ≤ 200，这个复杂度是可以接受的。

代码实现

class Solution {
public:
    int minimumChanges(string s, int k) {
        int n = s.length();
        
        // 计算每个子字符串变为半回文的最小代价
        vector<vector<int>> cost(n, vector<int>(n, INT_MAX));
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int len = j - i + 1;
                int minCost = INT_MAX;
                
                // 枚举所有可能的除数
                for (int d = 1; d < len; d++) {
                    if (len % d != 0) continue;
                    
                    int groups = d;
                    int groupSize = len / d;
                    int totalCost = 0;
                    
                    // 计算每组变为回文的代价
                    for (int g = 0; g < groups; g++) {
                        int groupCost = 0;
                        for (int l = 0, r = groupSize - 1; l < r; l++, r--) {
                            int pos1 = i + g + l * d;
                            int pos2 = i + g + r * d;
                            if (s[pos1] != s[pos2]) {
                                groupCost++;
                            }
                        }
                        totalCost += groupCost;
                    }
                    
                    minCost = min(minCost, totalCost);
                }
                
                cost[i][j] = minCost;
            }
        }
        
        // 动态规划
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));
        dp[n][0] = 0;
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j <= k && j <= n - i; j++) {
                for (int x = i + 1; x < n && x - i + 1 <= n - i - j + 1; x++) {
                    if (dp[x + 1][j - 1] != INT_MAX && cost[i][x] != INT_MAX) {
                        dp[i][j] = min(dp[i][j], dp[x + 1][j - 1] + cost[i][x]);
                    }
                }
            }
        }
        
        return dp[0][k];
    }
};

class Solution:
    def minimumChanges(self, s: str, k: int) -> int:
        n = len(s)
        
        # 计算每个子字符串变为半回文的最小代价
        cost = [[float('inf')] * n for _ in range(n)]
        
        for i in range(n):
            for j in range(i + 1, n):
                length = j - i + 1
                min_cost = float('inf')
                
                # 枚举所有可能的除数
                for d in range(1, length):
                    if length % d != 0:
                        continue
                    
                    groups = d
                    group_size = length // d
                    total_cost = 0
                    
                    # 计算每组变为回文的代价
                    for g in range(groups):
                        group_cost = 0
                        l, r = 0, group_size - 1
                        while l < r:
                            pos1 = i + g + l * d
                            pos2 = i + g + r * d
                            if s[pos1] != s[pos2]:
                                group_cost += 1
                            l += 1
                            r -= 1
                        total_cost += group_cost
                    
                    min_cost = min(min_cost, total_cost)
                
                cost[i][j] = min_cost
        
        # 动态规划
        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
        dp[n][0] = 0
        
        for i in range(n - 1, -1, -1):
            for j in range(1, min(k + 1, n - i + 1)):
                for x in range(i + 1, n):
                    if x - i + 1 <= n - i - j + 1:
                        if dp[x + 1][j - 1] != float('inf') and cost[i][x] != float('inf'):
                            dp[i][j] = min(dp[i][j], dp[x + 1][j - 1] + cost[i][x])
        
        return dp[0][k]

public class Solution {
    public int MinimumChanges(string s, int k) {
        int n = s.Length;
        
        // 计算每个子字符串变为半回文的最小代价
        int[,] cost = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cost[i, j] = int.MaxValue;
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int length = j - i + 1;
                int minCost = int.MaxValue;
                
                // 枚举所有可能的除数
                for (int d = 1; d < length; d++) {
                    if (length % d != 0) continue;
                    
                    int groups = d;
                    int groupSize = length / d;
                    int totalCost = 0;
                    
                    // 计算每组变为回文的代价
                    for (int g = 0; g < groups; g++) {
                        int groupCost = 0;
                        for (int l = 0, r = groupSize - 1; l < r; l++, r--) {
                            int pos1 = i + g + l * d;
                            int pos2 = i + g + r * d;
                            if (s[pos1] != s[pos2]) {
                                groupCost++;
                            }
                        }
                        totalCost += groupCost;
                    }
                    
                    minCost = Math.Min(minCost, totalCost);
                }
                
                cost[i, j] = minCost;
            }
        }
        
        // 动态规划
        int[,] dp = new int[n + 1, k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i, j] = int.MaxValue;
            }
        }
        dp[n, 0] = 0;
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j <= k && j <= n - i; j++) {
                for (int x = i + 1; x < n && x - i + 1 <= n - i - j + 1; x++) {
                    if (dp[x + 1, j - 1] != int.MaxValue && cost[i, x] != int.MaxValue) {
                        dp[i, j] = Math.Min(dp[i, j], dp[x + 1, j - 1] + cost[i, x]);
                    }
                }
            }
        }
        
        return dp[0, k];
    }
}

var minimumChanges = function(s, k) {
    const n = s.length;
    
    // 计算每个子字符串变为半回文的最小代价
    const cost = Array(n).fill().map(() => Array(n).fill(Infinity));
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const length = j - i + 1;
            let minCost = Infinity;
            
            // 枚举所有可能的除数
            for (let d = 1; d < length; d++) {
                if (length % d !== 0) continue;
                
                const groups = d;
                const groupSize = Math.floor(length / d);
                let totalCost = 0;
                
                // 计算每组变为回文的代价
                for (let g = 0; g < groups; g++) {
                    let groupCost = 0;
                    for (let l = 0, r = groupSize - 1; l < r; l++, r--) {
                        const pos1 = i + g + l * d;
                        const pos2 = i + g + r * d;
                        if (s[pos1] !== s[pos2]) {
                            groupCost++;
                        }
                    }
                    totalCost += groupCost;
                }
                
                minCost = Math.min(minCost, totalCost);
            }
            
            cost[i][j] = minCost;
        }
    }
    
    // 动态规划
    const dp = Array(n + 1).fill().map(() => Array(k + 1).fill(Infinity));
    dp[n][0] = 0;
    
    for (let i = n - 1; i >= 0; i--) {
        for (let j = 1; j <= k && j <= n - i; j++) {
            for (let x = i + 1; x < n && x - i + 1 <= n - i - j + 1; x++) {
                if (dp[x + 1][j - 1] !== Infinity && cost[i][x] !== Infinity) {
                    dp[i][j] = Math.min(dp[i][j], dp[x + 1][j - 1] + cost[i][x]);
                }
            }
        }
    }
    
    return dp[0][k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n³ × d(n) + n² × k)，其中 n 是字符串长度，d(n) 是除数个数，k 是分割数量
空间复杂度O(n² + n × k)，用于存储预处理的代价数组和 DP 数组

相关题目