Hard

题目描述

给定一个字符串 s。

如果字符串 t 中所有字符出现的次数都相同，则称字符串 t 是"好的"。

你可以执行以下操作任意次数：

  • 从 s 中删除一个字符。
  • 在 s 中插入一个字符。
  • 将 s 中的一个字符更改为字母表中的下一个字母。

注意，你不能使用第三种操作将 ‘z’ 更改为 ‘a’。

返回使 s 变为"好的"字符串所需的最小操作数。

示例 1：

输入：s = “acab” 输出：1 解释： 我们可以通过删除字符 ‘a’ 的一个出现次数来使 s 变为好的。

示例 2：

输入：s = “wddw” 输出：0 解释： 我们不需要执行任何操作，因为 s 最初就是好的。

示例 3：

输入：s = “aaabc” 输出：2 解释： 我们可以通过应用以下操作使 s 变为好的：

  • 将 ‘a’ 的一个出现次数更改为 ‘b’
  • 插入一个 ‘c’ 到 s 中

约束条件：

  • 3 <= s.length <= 2 * 10^4
  • s 只包含小写英文字母。

解题思路

这道题的关键思路是将字符串操作转化为频率数组操作。我们需要理解三种操作对字符频率的影响：

  1. 删除字符：使某个字符的频率减1
  2. 插入字符：使某个字符的频率加1
  3. 字符变换：使某个字符频率减1，同时使其后继字符频率加1

目标是使所有非零频率都相等。设这个目标频率为 c，我们需要枚举所有可能的 c 值。

核心观察：

  • 字符变换操作可以看作是频率的"流动"，从前面的字符流向后面的字符
  • 我们可以使用动态规划，dp[i] 表示处理前 i 个字符（a到第i个字符）使其满足条件的最小操作数
  • 对于每个位置 i，我们需要决定该位置的最终频率是 0 还是 c

状态转移时考虑：

  • 如果当前位置频率设为 0：需要删除所有当前字符
  • 如果当前位置频率设为 c：可能需要从前面"流入"一些频率，或者删除多余的频率

通过枚举目标频率 c 和动态规划，我们可以找到最小操作数。

代码实现

class Solution {
public:
    int makeStringGood(string s) {
        vector<int> freq(26, 0);
        for (char c : s) {
            freq[c - 'a']++;
        }
        
        int n = s.length();
        int result = n; // 最坏情况：删除所有字符
        
        // 枚举目标频率 c
        for (int c = 1; c <= n; c++) {
            vector<int> dp(27, INT_MAX);
            dp[0] = 0;
            
            for (int i = 1; i <= 26; i++) {
                // 选择频率为 0
                dp[i] = min(dp[i], dp[i-1] + freq[i-1]);
                
                // 选择频率为 c
                int flow = 0;
                int cost = 0;
                for (int j = i; j >= 1; j--) {
                    flow += freq[j-1];
                    cost += max(0, flow - c);
                    if (dp[j-1] != INT_MAX) {
                        dp[i] = min(dp[i], dp[j-1] + cost + max(0, c - flow));
                    }
                }
            }
            
            result = min(result, dp[26]);
        }
        
        return result;
    }
};

class Solution:
    def makeStringGood(self, s: str) -> int:
        freq = [0] * 26
        for c in s:
            freq[ord(c) - ord('a')] += 1
        
        n = len(s)
        result = n  # 最坏情况：删除所有字符
        
        # 枚举目标频率 c
        for c in range(1, n + 1):
            dp = [float('inf')] * 27
            dp[0] = 0
            
            for i in range(1, 27):
                # 选择频率为 0
                dp[i] = min(dp[i], dp[i-1] + freq[i-1])
                
                # 选择频率为 c
                flow = 0
                cost = 0
                for j in range(i, 0, -1):
                    flow += freq[j-1]
                    cost += max(0, flow - c)
                    if dp[j-1] != float('inf'):
                        dp[i] = min(dp[i], dp[j-1] + cost + max(0, c - flow))
            
            result = min(result, dp[26])
        
        return result

public class Solution {
    public int MakeStringGood(string s) {
        int[] freq = new int[26];
        foreach (char c in s) {
            freq[c - 'a']++;
        }
        
        int n = s.Length;
        int result = n; // 最坏情况：删除所有字符
        
        // 枚举目标频率 c
        for (int c = 1; c <= n; c++) {
            int[] dp = new int[27];
            for (int i = 1; i <= 26; i++) {
                dp[i] = int.MaxValue;
            }
            
            for (int i = 1; i <= 26; i++) {
                // 选择频率为 0
                dp[i] = Math.Min(dp[i], dp[i-1] + freq[i-1]);
                
                // 选择频率为 c
                int flow = 0;
                int cost = 0;
                for (int j = i; j >= 1; j--) {
                    flow += freq[j-1];
                    cost += Math.Max(0, flow - c);
                    if (dp[j-1] != int.MaxValue) {
                        dp[i] = Math.Min(dp[i], dp[j-1] + cost + Math.Max(0, c - flow));
                    }
                }
            }
            
            result = Math.Min(result, dp[26]);
        }
        
        return result;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var makeStringGood = function(s) {
    const freq = new Array(26).fill(0);
    for (const c of s) {
        freq[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    const n = s.length;
    let result = n; // 最坏情况：删除所有字符
    
    // 枚举目标频率 c
    for (let c = 1; c <= n; c++) {
        const dp = new Array(27).fill(Infinity);
        dp[0] = 0;
        
        for (let i = 1; i <= 26; i++) {
            // 选择频率为 0
            dp[i] = Math.min(dp[i], dp[i-1] + freq[i-1]);
            
            // 选择频率为 c
            let flow = 0;
            let cost = 0;
            for (let j = i; j >= 1; j--) {
                flow += freq[j-1];
                cost += Math.max(0, flow - c);
                if (dp[j-1] !== Infinity) {
                    dp[i] = Math.min(dp[i], dp[j-1] + cost + Math.max(0, c - flow));
                }
            }
        }
        
        result = Math.min(result, dp[26]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n² × 26)外层枚举目标频率O(n)，内层动态规划O(26²)
空间复杂度O(26)存储字符频率和DP数组

相关题目