题目链接

小红的字符串

题目描述

小红有一个长度为 的小写字母字符串 。她可以对字符串进行任意次操作：选择一个下标 ，将字符 循环右移到字母表中的下一个字母（例如 'a' 变成 'b'，'z' 变成 'a'）。

请计算，使字符串 变为回文串所需的最少操作次数。

解题思路

本题的目标是，用最少的操作次数将一个字符串变为回文串。操作的本质是改变字符。

1. 回文串的性质 一个字符串是回文串，意味着对于所有 ，第 个字符都必须和倒数第 个字符（即下标为 的字符）相同。因此，我们的任务就是让每一对对称位置的字符 变得相同。

2. 计算单对字符的最小操作数 总的最少操作次数，等于所有对称字符对 各自达成一致所需的最少操作次数之和。

现在我们来考虑如何让两个字符 和 变得相同。操作是“循环右移”，这可以理解为在字母表 'a' 到 'z' 这个环上向前移动。

  • 我们可以将 不断右移，直到它变成 。
  • 我们也可以将 不断右移，直到它变成 。

最优解一定是这两种方式之一，而不会是把两个字符都变成某个第三种字符。 要计算这两个操作的次数，我们可以将 'a' 到 'z' 映射为数字 0 到 25。

  • 从 变到 的操作次数是 。
  • 从 变到 的操作次数是 。 一个更简单的计算方法是，先计算两个字符在字母表中的直接距离 dist = |pos(c1) - pos(c2)|。那么，在环上的最短距离就是 min(dist, 26 - dist)。

例如，对于 'a' 和 'd'：

  • 位置分别是 0 和 3。
  • 直接距离是 。
  • 环上距离是 。所以最少需要3次操作（'a' 'b' 'c' 'd'）。

3. 算法步骤

  1. 使用双指针，一个指针 left 从字符串头部开始，另一个指针 right 从尾部开始。
  2. 当 left < right 时，循环执行以下操作：
    • 取出对称位置的两个字符 和 。
    • 计算它们在字母表环上的最短距离。
    • 将这个距离累加到总操作次数 total_ops 中。
    • 将 left 指针右移一位，right 指针左移一位。
  3. 循环结束后，total_ops 就是所需的最小总操作次数。

代码

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

using namespace std;

int main() {
    string s;
    cin >> s;
    
    long long total_ops = 0;
    int left = 0;
    int right = s.length() - 1;
    
    while (left < right) {
        int pos1 = s[left] - 'a';
        int pos2 = s[right] - 'a';
        
        int diff = abs(pos1 - pos2);
        total_ops += min(diff, 26 - diff);
        
        left++;
        right--;
    }
    
    cout << total_ops << endl;
    
    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        long totalOps = 0;
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right) {
            int pos1 = s.charAt(left) - 'a';
            int pos2 = s.charAt(right) - 'a';
            
            int diff = Math.abs(pos1 - pos2);
            totalOps += Math.min(diff, 26 - diff);
            
            left++;
            right--;
        }
        
        System.out.println(totalOps);
    }
}

import sys

def solve():
    s = sys.stdin.readline().strip()
    
    total_ops = 0
    left, right = 0, len(s) - 1
    
    while left < right:
        pos1 = ord(s[left]) - ord('a')
        pos2 = ord(s[right]) - ord('a')
        
        diff = abs(pos1 - pos2)
        total_ops += min(diff, 26 - diff)
        
        left += 1
        right -= 1
        
    print(total_ops)

solve()

算法及复杂度

  • 算法：双指针
  • 时间复杂度：我们使用双指针遍历了字符串的一半。设字符串长度为 ，则时间复杂度为 。
  • 空间复杂度：需要 的空间来存储输入的字符串。