题目链接

小红的回文串

题目描述

给定一个长度为 的字符串，你有两种操作：

  1. 循环移位：将字符串的第一个字母移动到末尾。
  2. 修改：将字符串中的任意一个字符修改为任意其他小写字母。

目标是使用最少的操作次数，将原字符串变为一个回文串。

解题思路

这是一个典型的优化问题，我们需要在两种不同类型的操作（循环移位和修改）之间找到一个最优的平衡点。

1. 分解问题

我们可以将问题分解为两部分：首先执行若干次“循环移位”操作，得到一个中间状态的字符串；然后，对这个中间状态的字符串执行若干次“修改”操作，使其最终变为回文串。

总操作数 = (循环移位次数) + (修改次数)

我们的目标是最小化这个总操作数。

2. 枚举所有可能的中间状态

“循环移位”操作实际上是对字符串进行旋转。一个长度为 的字符串，总共有 种不同的旋转状态（包括不旋转）。我们可以枚举所有这些状态。

假设我们执行了 次循环移位操作（其中 ）：

  • 移位成本：执行了 次操作，成本为 。
  • 得到的新字符串 s_k：这是原字符串 s 的一个循环同构体。例如，如果 s = "abcde" 且 k=2，则 s_k = "cdeab"。
  • 修改成本：现在我们需要计算将 s_k 变为回文串所需的最少修改次数。这个成本可以通过比较字符串两端的字符来计算。我们用双指针，一个从头开始，一个从尾开始，向中间移动。每当遇到一对不匹配的字符（s_k[i] != s_k[n-1-i]），修改成本就加 1。
  • 当前总成本：对于这个特定的 ，总成本为 k + (s_k 的修改成本)。

3. 寻找全局最优解

我们只需要遍历所有可能的循环移位次数 （从 0 到 ），计算出每种情况下的总成本，然后取其中的最小值即可。

算法步骤

  1. 初始化 min_ops 为一个极大值。
  2. 循环遍历 k from 0 to n-1： a. 计算当前移位成本 ops1 = k。 b. 生成旋转 次后的新字符串 s_k。 c. 计算将 s_k 变为回文的修改成本 ops2。 d. 计算当前总成本 total_ops = ops1 + ops2。 e. 更新 min_ops = min(min_ops, total_ops)。
  3. 循环结束后，min_ops 就是答案。

代码

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

using namespace std;

// Function to calculate modification cost for a string to be a palindrome
int calculate_diff(const string& s) {
    int diff = 0;
    int n = s.length();
    for (int i = 0; i < n / 2; ++i) {
        if (s[i] != s[n - 1 - i]) {
            diff++;
        }
    }
    return diff;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    string s;
    cin >> s;

    int min_ops = -1;

    for (int k = 0; k < n; ++k) {
        // Create the rotated string
        string rotated_s = s.substr(k) + s.substr(0, k);

        // Cost of rotation is k
        int ops1 = k;
        // Cost of modification
        int ops2 = calculate_diff(rotated_s);

        int total_ops = ops1 + ops2;

        if (min_ops == -1 || total_ops < min_ops) {
            min_ops = total_ops;
        }
    }

    cout << min_ops << endl;

    return 0;
}

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

public class Main {

    // Function to calculate modification cost for a string to be a palindrome
    private static int calculateDiff(String s) {
        int diff = 0;
        int n = s.length();
        for (int i = 0; i < n / 2; i++) {
            if (s.charAt(i) != s.charAt(n - 1 - i)) {
                diff++;
            }
        }
        return diff;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();

        int minOps = Integer.MAX_VALUE;

        for (int k = 0; k < n; k++) {
            // Create the rotated string
            String rotatedS = s.substring(k) + s.substring(0, k);

            // Cost of rotation is k
            int ops1 = k;
            // Cost of modification
            int ops2 = calculateDiff(rotatedS);

            int totalOps = ops1 + ops2;
            minOps = Math.min(minOps, totalOps);
        }

        System.out.println(minOps);
    }
}

import sys

def calculate_diff(s):
    """Calculates modification cost for a string to be a palindrome."""
    diff = 0
    n = len(s)
    for i in range(n // 2):
        if s[i] != s[n - 1 - i]:
            diff += 1
    return diff

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        s = sys.stdin.readline().strip()
    except (IOError, ValueError):
        return

    min_ops = float('inf')

    for k in range(n):
        # Create the rotated string
        rotated_s = s[k:] + s[:k]
        
        # Cost of rotation is k
        ops1 = k
        # Cost of modification
        ops2 = calculate_diff(rotated_s)
        
        total_ops = ops1 + ops2
        min_ops = min(min_ops, total_ops)
        
    print(min_ops)

solve()

算法及复杂度

  • 算法：枚举

  • 时间复杂度：。

    • 我们有一个外层循环，遍历所有 种可能的旋转状态。
    • 在每次循环内部，生成旋转后的字符串需要 的时间，计算修改成本也需要 的时间。
    • 因此，总时间复杂度为 。

  • 空间复杂度：。

    • 需要 的空间来存储原始字符串和每次生成的旋转字符串。