2025-07-03：使字符频率相等的最少操作次数。用go语言，给定一个字符串 s。

如果某个字符串 t 中所有字符的出现次数相同，则称这个字符串 t 是“好”的。

你可以对 s 执行以下操作，操作次数不限：

• 删除 s 中的任意一个字符；

• 向 s 中添加任意一个字符；

• 将 s 中的某个字符修改为字母表中紧接着的下一个字母（注意，字符 ‘z’ 不能变成 ‘a’）。

请问，至少需要进行多少次操作，才能使 s 变成一个“好”的字符串？

1 <= s.length <= 20000。

s 只包含小写英文字母。

输入：s = “aaabc”。

输出：2。

解释：

通过以下操作，将 s 变好：

将一个 ‘a’ 变为 ‘b’ 。

往 s 中插入一个 ‘c’ 。

题目来自力扣3389。

分步骤描述过程：

1. 统计字符频率：

   • 首先，代码统计字符串 s 中每个小写字母的出现次数，存储在一个长度为 26 的数组 cnt 中。例如，对于 s = "aaabc"，cnt 数组的前几个元素会是 cnt['a'-'a'] = 3，cnt['b'-'a'] = 1，cnt['c'-'a'] = 1，其余为 0。

2. 生成候选目标频率：

   • 目标是让所有字符的频率相同（即“好”字符串）。为了找到可能的目标频率，代码生成一组候选值 targets。这些候选值包括：
     • 每个字符的原始频率（cnt[i]）。
     • 相邻字符频率的和（cnt[i-1] + cnt[i]）。
     • 相邻字符频率的平均值（向下和向上取整，即 (x+y)/2 和 (x+y+1)/2）。
   • 例如，对于 s = "aaabc"，cnt['a'] = 3 和 cnt['b'] = 1，生成的候选目标可能包括 3、1、4（3+1）、2（(3+1)/2）等。

3. 动态规划计算最小操作次数：

   • 对于每一个候选目标频率 target，代码使用动态规划计算将 cnt 数组调整为所有字符频率为 target 或 0（表示删除该字符）的最小操作次数。
   • 动态规划数组 f 的长度为 27（覆盖所有 26 个字母和一个边界条件），f[i] 表示从第 i 个字母到第 25 个字母（‘z’）调整为 target 或 0 的最小操作次数。
   • 从最后一个字母 ‘z’ 开始向前计算：
     • 对于字母 i，可以选择：
       1. 将其频率调整为 target 或 0（删除），操作次数为 min(cnt[i], abs(cnt[i] - target))。
       2. 如果当前字母 i 和下一个字母 i+1 的频率可以组合调整（例如，通过修改或合并操作），则尝试这种组合调整的可能。
     • 动态规划状态转移会综合考虑这些选择的最小操作次数。
   • 最终，f[0] 表示将所有字母调整为 target 或 0 的最小操作次数。

4. 选择最小操作次数：

   • 遍历所有候选目标频率 target，计算对应的 f[0]，并记录最小的 f[0] 作为答案。
   • 例如，对于 s = "aaabc"，候选目标 target = 2 时，可以通过将 1 个 ‘a’ 改为 ‘b’（操作 1）和添加 1 个 ‘c’（操作 1），总操作次数为 2。

时间复杂度和空间复杂度：

• 时间复杂度：
  • 统计字符频率：O(n)，其中 n 是字符串长度。
  • 生成候选目标频率：O(26) = O(1)，因为字母表大小固定。
  • 动态规划过程：对于每个候选目标频率（最多 O(26) 个），动态规划的计算是 O(26) 的，因此总时间复杂度为 O(26^2) = O(1)。
  • 总时间复杂度：O(n + 1 + 1) = O(n)。
• 空间复杂度：
  • 统计字符频率的数组 cnt：O(26) = O(1)。
  • 候选目标频率集合 targets：最多 O(26) 个候选目标，O(1)。
  • 动态规划数组 f：O(26) = O(1)。
  • 总空间复杂度：O(1)。

总结：

• 该算法通过统计字符频率、生成候选目标频率，并使用动态规划计算最小操作次数，高效地解决了问题。
• 时间复杂度和空间复杂度均为线性（O(n)）和常数（O(1)），适用于输入规模较大的情况（如题目中的 n ≤ 20000）。

Go完整代码如下：

package main

import (
	"fmt"
)

func makeStringGood(s string) int {
	cnt := [26]int{}
	for _, b := range s {
		cnt[b-'a']++
	}

	targets := map[int]struct{}{}
	targets[cnt[0]] = struct{}{}
	for i := 1; i < 26; i++ {
		x, y := cnt[i-1], cnt[i]
		targets[y] = struct{}{}
		targets[x+y] = struct{}{}
		targets[(x+y)/2] = struct{}{}
		targets[(x+y+1)/2] = struct{}{}
	}

	ans := len(s) // target = 0 时的答案
	f := [27]int{}
	for target := range targets {
		f[25] = min(cnt[25], abs(cnt[25]-target))
		for i := 24; i >= 0; i-- {
			x := cnt[i]
			if x == 0 {
				f[i] = f[i+1]
				continue
			}
			// 单独操作 x（变成 target 或 0）
			f[i] = f[i+1] + min(x, abs(x-target))
			// x 变成 target 或 0，y 变成 target
			y := cnt[i+1]
			if 0 < y && y < target { // 只有当 y 需要变大时，才去执行第三种操作
				if x > target { // x 变成 target
					f[i] = min(f[i], f[i+2]+max(x-target, target-y))
				} else { // x 变成 0
					f[i] = min(f[i], f[i+2]+max(x, target-y))
				}
			}
		}
		ans = min(ans, f[0])
	}
	return ans
}

func abs(x int) int { if x < 0 { return -x }; return x }


func main() {
	s := "aaabc"
	result := makeStringGood(s)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def make_string_good(s: str) -> int:
    cnt = [0] * 26
    for ch in s:
        cnt[ord(ch) - ord('a')] += 1

    targets = set()
    targets.add(cnt[0])
    for i in range(1, 26):
        x, y = cnt[i - 1], cnt[i]
        targets.add(y)
        targets.add(x + y)
        targets.add((x + y) // 2)
        targets.add((x + y + 1) // 2)

    ans = len(s)  # 当 target = 0 时的答案
    f = [0] * 27

    def min_val(a, b):
        return a if a < b else b

    def abs_val(x):
        return x if x >= 0 else -x

    def max_val(a, b):
        return a if a > b else b

    for target in targets:
        f[25] = min_val(cnt[25], abs_val(cnt[25] - target))
        for i in range(24, -1, -1):
            x = cnt[i]
            if x == 0:
                f[i] = f[i + 1]
                continue

            # 单独操作 x（变成 target 或 0）
            f[i] = f[i + 1] + min_val(x, abs_val(x - target))

            # x 变成 target 或 0，y 变成 target
            y = cnt[i + 1]
            if 0 < y < target:  # 只有当 y 需要变大时，才去执行第三种操作
                if x > target:  # x 变成 target
                    f[i] = min_val(f[i], f[i + 2] + max_val(x - target, target - y))
                else:  # x 变成 0
                    f[i] = min_val(f[i], f[i + 2] + max_val(x, target - y))

        ans = min_val(ans, f[0])

    return ans


if __name__ == "__main__":
    s = "aaabc"
    result = make_string_good(s)
    print(result)