解题思路

• 将 26 个小写字母看作首尾相接的环（a 与 z 相邻）。一次操作可把某个字母改成其相邻字母。
• 若把所有字符都改成同一个目标字母 t，把字符 c 改到 t 的最小代价为环形距离 dist(c,t) = min(|pos(c)-pos(t)|, 26 - |pos(c)-pos(t)|)，其中 pos(x)=ord(x)-ord('a')。
• 对每个目标字母 t ∈ [0..25] 累加整串的代价，取最小值即答案。
• 相关算法：枚举 + 环形距离（最短路等价为贪心选最近方向）。因为目标字母只有 26 个，复杂度近似线性。

复杂度分析

• 时间复杂度：对每个字符枚举 26 个目标字母，$O(26 \cdot n) = O(n)$（26 为常数）。
• 空间复杂度：$O(1)$。

代码实现

Python

# -*- coding: utf-8 -*-
import sys

# 计算把字符串 s 变为同一字母的最小操作次数
def min_ops(s: str) -> int:
    n = len(s)
    pos = [ord(ch) - ord('a') for ch in s]  # 每个字符的位置 0..25
    ans = 10**18
    for t in range(26):  # 枚举目标字母
        cur = 0
        for p in pos:
            d = abs(p - t)
            cur += min(d, 26 - d)  # 环形距离
        if cur < ans:
            ans = cur
    return ans

if __name__ == "__main__":
    # 读取一行仅含小写字母的字符串
    s = sys.stdin.readline().strip()
    print(min_ops(s))

Java

// ACM 风格，类名 Main
import java.io.*;

// 题面功能写在外部函数里
public class Main {
    // 计算最小操作次数
    static long minOps(String s) {
        int n = s.length();
        int[] pos = new int[n];
        for (int i = 0; i < n; i++) pos[i] = s.charAt(i) - 'a';
        long ans = Long.MAX_VALUE;

        // 枚举 26 个目标字母
        for (int t = 0; t < 26; t++) {
            long cur = 0;
            for (int p : pos) {
                int d = Math.abs(p - t);
                cur += Math.min(d, 26 - d); // 环形距离
            }
            if (cur < ans) ans = cur;
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        // 使用 BufferedReader 读取输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim(); // 一行小写字母
        System.out.println(minOps(s));
    }
}

C++

// ACM 风格，主函数中进行输入输出
#include <bits/stdc++.h>
using namespace std;

// 计算把字符串 s 变为同一字母的最小操作次数
long long min_ops(const string &s) {
    vector<int> pos; pos.reserve(s.size());
    for (char c : s) pos.push_back(c - 'a');

    long long ans = (long long)4e18;
    for (int t = 0; t < 26; ++t) {      // 枚举目标字母
        long long cur = 0;
        for (int p : pos) {
            int d = abs(p - t);
            cur += min(d, 26 - d);     // 环形距离
        }
        ans = min(ans, cur);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if (cin >> s) {
        cout << min_ops(s) << '\n';
    }
    return 0;
}

题目内容

对于一个小写字母而言，游游可以通过一次操作把这个字母变成相邻的字母。'$a$' 和 '$b$' 相邻，'$b$' 和 '$c$' 相邻，以此类推。特殊的，'$a$' 和 '$z$' 也是相邻的。可以认为，小写字母的相邻规则为一个环。

游游拿到了一个仅包含小写字母的字符串，她想知道，使得所有字母都相等至少要多少次操作?

输入描述

一个仅包含小写字母，长度不超过 $100000$ 的字符串。

输出描述

一个整数，代表最小的操作次数。

样例1

输入

yab

输出

3

说明

第一次操作，把 '$y$' 变成 '$z$' ，字符串变成了 "$zab$"

第二次操作，把 '$b$' 变成 '$a$' ，字符串变成了 "$zaa$”

第三次操作，把 '$z$' 变成 '$a$' ，字符串变成了 "$aaa$"