2024-09-21：用 go 语言，给定一个字符串 s，字符串中的每个字符要么是小写字母，要么是问号'?'。对于一个仅包含小写字母的字符串 t，我们定义 cost(i)为在 t 的前 i 个字符中与 t[i]相同的字符的出现次数。字符串 t 的分数是所有位置 i 的 cost(i)之和。现在的任务是用小写字母替换所有的问号'?'，使得字符串 s 的分数最小。如果有多个替换方案使得分数最小，那么返回字典序最小的一个。输入：s = "???"。输出： "abc"。解释：这个例子中，我们将 s 中的问号 '?' 替换得到 "abc" 。对于字符串 "abc" ，cost(0) = 0 ，cost(1) = 0 和 cost(2) = 0 。"abc" 的分数为 0 。其他修改 s 得到分数 0 的字符串为 "cba" ，"abz" 和 "hey" 。这些字符串中，我们返回字典序最小的。

大体步骤如下：

1.初始化一个大小为 27 的整型数组 freq，用于记录每个字符出现的次数，初始全部为 0，26 号位作为哨兵。

2.遍历字符串 s，若字符不是'?'，则在 freq 相应位置累加。

3.对 freq 数组进行排序，得到排序后的数组 f。

4.统计字符串 s 中问号'?'的个数 q，初始化 limit 和 extra 为 0。

5.从 1 开始遍历数组 f，计算每个字符值变化产生的增加的字符数 sum。

6.若问号数量小于等于 sum，则更新 limit 和 extra，并跳出循环。

7.根据 limit 和 extra 更新目标替换数组 target，将出现次数不超过 limit 的字符值更新为 limit，如果 extra 大于 0，则额外分配给字符值较小的字符。

8.遍历字符串 s，遇到问号'?'时用目标数组 target 替换，替换顺序为字典序最小。

9.返回替换后的字符串作为最终结果。

总体复杂度分析

• 时间复杂度：遍历字符串 s 的时间复杂度为 O(n)，排序时间复杂度为 O(nlogn)，整体时间复杂度为 O(nlogn)。

• 空间复杂度：除了字符串 s 本身外，额外使用了大小为 27 的整型数组 freq 和 target，以及一些辅助变量，总的额外空间复杂度较小，为 O(1)。

答案 2024-09-21：

chatgpt

题目来自 leetcode3081。

go 完整代码如下：

package main
import (  "fmt"  "math"  "slices"  "strings")
func minimizeStringValue(s string) string {  freq := [27]int{26: math.MaxInt / 26} // 哨兵  for _, c := range s {    if c != '?' {      freq[c-'a']++    }  }
  f := freq  slices.Sort(f[:])
  var limit, extra int  q := strings.Count(s, "?")  for i := 1; ; i++ {    sum := i * (f[i] - f[i-1])    if q <= sum {      limit, extra = f[i-1]+q/i, q%i      break    }    q -= sum  }
  target := freq  for i, c := range freq[:26] {    if c > limit {      continue    }    target[i] = limit    if extra > 0 { // 还可以多分配一个      extra--      target[i]++    }  }
  ans := []byte(s)  j := byte(0)  for i, c := range ans {    if c != '?' {      continue    }    for freq[j] == target[j] {      j++    }    freq[j]++    ans[i] = 'a' + j  }  return string(ans)}
func main() {  s := "???"  fmt.Println(minimizeStringValue(s))}