2026-02-05：转换字符串的最小操作次数。用go语言，给定一个只含小写字母的字符串 s。你可以重复做这样的事情任意次：从当前字符串中选出

福大大架构师每日一题

发布于 2026-02-09 14:49:47

850

2026-02-05：转换字符串的最小操作次数。用go语言，给定一个只含小写字母的字符串 s。你可以重复做这样的事情任意次：从当前字符串中选出一种出现过的字母，把该字母的所有出现位置一次性都替换为字母表中的下一个字母（字母表循环，'z' 的下一个是 'a'）。问：要把 s 变成全由字符 'a' 组成，最少需要多少次这样的操作？

1 <= s.length <= 5 * 100000。

s 仅由小写英文字母组成。

输入： s = "yz"。

输出： 2。

解释：

将 'y' 变为 'z'，得到 "zz"。

将 'z' 变为 'a'，得到 "aa"。

因此，答案是 2。

题目来自力扣3675。

🔍 步骤一：理解操作规则

题目允许的操作是：每次选择字符串中出现过的一种字母，将该字母在所有出现的位置上一次性替换为字母表中的下一个字母。字母表是循环的，即 'z' 的下一个是 'a'。我们的目标是将字符串 s 变成全由字符 'a' 组成。

🎯 步骤二：确定关键观察点

1. 操作的连锁效应：由于每次操作是针对同一种字母的所有出现位置，并且字母表是循环的，因此整个转换过程可以看作是需要将字符串中所有非 'a' 的字母“推动”到 'a'。
2. 最小起始点的发现：一个关键的观察是，整个转换过程所需的操作次数，实际上取决于字符串中需要被转换的字母里，在字母表上最小的那个字母。这是因为：
- • 要将一个字母 c 变成 'a'，需要进行的操作次数是 ('a' - c + 26) % 26。由于字母表循环，这个计算等价于 'z' + 1 - c（如代码中所用）。
- • 如果字符串中同时存在多个不同的字母，比如 'b'和'c'，你不能只把'b'变成'a'就结束，因为'c'还在。你必须先把'c'变成'd'（或更后面的字母），再变成'a'，这个过程会再次“产生”非'a'的字母（例如，'c'变成'd'时，'d'对于已经变成'a'的'b' 来说又是一个需要被处理的字母）。
- • 最有效的方式是从字母表中最小的那个非 'a' 字母开始，依次将其推动到 'a'。这个最小的字母（记为 minC）决定了整个链条的起点。你需要将 minC 变成 'a'，而在这个过程中，所有比 minC 大的字母也会被连带处理（因为它们也会被操作推动）。最终，将 minC 成功变为 'a' 所需的操作次数，就是将所有字母变为 'a' 所需的最少操作次数。

🔄 步骤三：算法过程描述

基于上述观察，代码的逻辑非常简洁：

1. 初始化：变量 minC 被初始化为 'z' + 1（即一个比 'z' 大的值，例如 '{'），目的是为了在后续比较中能被任何小写字母替换。
2. 寻找最小字母：遍历字符串 s 中的每一个字符 c。
- • 如果当前字符 c 不是 'a'，就比较 c 和当前记录的 minC，将较小的值赋给 minC。
- • 这里有一个优化：一旦在遍历过程中发现 minC 已经是 'b'，就可以立即终止循环。因为 'b' 是仅次于 'a' 的最小字母，不可能找到比 'b' 更小的非 'a' 字母了。这可以减少不必要的遍历。
3. 计算操作次数：遍历结束后，如果字符串中所有字符都是'a'（即minC仍为初始值'z' + 1），则不需要任何操作，返回0。否则，最少的操作次数就是'z' + 1 - minC。这个计算的含义是，将字母minC循环推动到'a'需要走完从minC到'z'再到'a'的路径。例如，当minC是'y'时，'z' + 1 - 'y' = 2，即'y'->'z'（1次操作），'z'->'a'（1次操作），总共2次。

⏱️ 复杂度分析

• 总的时间复杂度：O(n)，其中 n 是字符串 s 的长度。算法主要消耗在遍历字符串以寻找最小的非 'a' 字符上。虽然在最坏情况下（字符串中不含 'b'）需要遍历整个字符串，但平均情况下由于存在提前终止的优化（找到 'b' 就退出），效率很高。
• 总的额外空间复杂度：O(1)。算法只使用了固定数量的额外变量（如 minC），与输入字符串的长度 n 无关。空间消耗是常数级别的。

Go完整代码如下：

package main

import (
    "fmt"
)

func minOperations(s string)int {
    minC := 'z' + 1
    for _, c := range s {
        if c != 'a' {
            minC = min(minC, c)
            if minC == 'b' {
                break
            }
        }
    }
    returnint('z' + 1 - minC)
}

func main() {
    s := "yz"
    result := minOperations(s)
    fmt.Println(result)
}

Python完整代码如下：

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

def min_operations(s: str) -> int:
    min_c = ord('z') + 1
    for c in s:
        if c != 'a':
            # 获取字符的 ASCII 码值
            c_val = ord(c)
            min_c = min(min_c, c_val)
            if min_c == ord('b'):
                break
    return ord('z') + 1 - min_c

def main():
    s = "yz"
    result = min_operations(s)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <string>
#include <algorithm>

int minOperations(const std::string& s) {
    char minC = 'z' + 1;
    for (char c : s) {
        if (c != 'a') {
            minC = std::min(minC, c);
            if (minC == 'b') {
                break;
            }
        }
    }
    return static_cast<int>('z' + 1 - minC);
}

int main() {
    std::string s = "yz";
    int result = minOperations(s);
    std::cout << result << std::endl;
    return0;
}