2024-11-25：满足距离约束且字典序最小的字符串。用go语言，给定一个字符串 s 和一个整数 k，我们需要定义一个函数 distance(s1, s2) 来计算两个长度相同的字符串 s1 和 s2 之间的距离。这个距离的定义是：对于每个索引 i（范围从 0 到 n-1），找出字符 s1[i] 和 s2[i] 之间的最小循环距离，并将这些最小距离相加。

例如：

1.distance(“ab”, “cd”) 的结果是 4，因为 ‘a’ 到 ‘c’ 的最小距离是 2，‘b’ 到 ‘d’ 的最小距离也是 2，故总和为 4。

2.distance(“a”, “z”) 的结果是 1，因为 ‘a’ 到 ‘z’ 的最小距离是 1。

我们可以对字符串 s 进行多次操作，每次操作可以将字符串中的一个字符替换成任意小写字母。我们的目标是找到一个字典序最小的字符串 t，使得 distance(s, t) <= k。

输入：s = “zbbz”, k = 3。

输出：“aaaz”。

解释：在这个例子中，可以执行以下操作：

将 s[0] 改为 ‘a’ ，s 变为 “abbz” 。

将 s[1] 改为 ‘a’ ，s 变为 “aabz” 。

将 s[2] 改为 ‘a’ ，s 变为 “aaaz” 。

“zbbz” 和 “aaaz” 之间的距离等于 k = 3 。

可以证明 “aaaz” 是在任意次操作后能够得到的字典序最小的字符串。

因此，答案是 “aaaz” 。

答案2024-11-25：

chatgpt

题目来自leetcode3106。

大体步骤如下：

1.距离定义：

• 首先要明确 distance(s1, s2) 的定义。对于两个字符串 s1 和 s2，其对应字符之间的最小循环距离是通过计算它们在字母表中的距离来确定的。具体来说，对于任意字符 a 和 b，它们的循环距离可通过如下方式计算：
  $\text{distance}(a, b) = \min(|a - b|, 26 - |a - b|)$

• 这里，|a - b| 是标准距离，而 26 - |a - b| 是通过绕回字母表起始点（即从 ‘z’ 回到 ‘a’）而得的循环距离。

2.初始化变量：

• 将输入字符串 s 保存在一个字符数组或切片中，以便于后续对字符的逐一处理。

• 变量 k 用以跟踪可用的距离预算。

3.遍历字符：

• 使用一个循环遍历字符串 s 中的所有字符。在每一次迭代中，都检查当前字符 s[i] 到目标字符 'a' 的距离。

• 对于当前字符 s[i]，计算它到 'a' 的距离：
  $\text{distance}(s[i], 'a') = \min(s[i] - 'a', 'z' - s[i] + 1)$

• 如果到 a 的变换距离小于等于当前的 k，则将字符替换为 'a' 并减少 k 的值。

• 如果到 'a' 的变换距离大于 k，则利用剩下的距离 k 来进行字符替换。将当前字符替换成计算后得到的新字符：
  $\text{新字符} = s[i] - k$

• 在这个字符替换后，结束当前循环，因为我们只能用完 k 次变换。

4.终止条件：

• 如果在某次迭代中，剩余的 k 使得字符不能完全变为 'a'，根据剩余距离变更该字符并终止更改后续的字符，从而保持其字典序最小。

5.结果输出：

• 一旦所有字符都被处理，构造出最终的字符串并返回。

时间复杂度和空间复杂度分析

• 时间复杂度：

  • 在最坏情况下，需要遍历整个字符串一次，因此时间复杂度是 (O(n))，其中 (n) 是字符串 s 的长度。

• 空间复杂度：

  • 由于我们需要一个与输入字符串等长的新字符数组来进行逐字符的替换，空间复杂度同样是 (O(n))。此外，使用的变量如 k 和 dis 等占用常数空间，因此整体额外空间复杂度为 (O(n))。

Go完整代码如下：

package main

import "fmt"

func getSmallestString(s string, k int) string {
	runes := []rune(s)
	for i := 0; i < len(runes); i++ {
		dis := min(int(runes[i]-'a'), int('z'-runes[i]+1))
		if dis <= k {
			runes[i] = 'a'
			k -= dis
		} else {
			runes[i] = rune(int(runes[i]) - k)
			break
		}
	}
	return string(runes)
}

func main() {
	s := "zbbz"
	k := 3
	fmt.Println(getSmallestString(s, k))
}

Rust完整代码如下：

fn get_smallest_string(s: &str, k: i32) -> String {
    let mut runes: Vec<char> = s.chars().collect();
    let mut k = k;

    for i in 0..runes.len() {
        let dis = std::cmp::min(runes[i] as i32 - 'a' as i32, 'z' as i32 - runes[i] as i32 + 1);
        if dis <= k {
            runes[i] = 'a';
            k -= dis;
        } else {
            let a = runes[i] as i32 - k as i32;
            runes[i] = (runes[i] as i32 - k as i32)as u8 as char;
            break;
        }
    }

    runes.iter().collect()
}

fn main() {
    let s = "zbbz";
    let k = 3;
    println!("{}", get_smallest_string(s, k));
}