题目思路

step1:贪心

由于字符串经过修改一定为回文串，且最多修改两次，所以原字符串位置$i$与对称位置$n-i-1$不一样的个数最多为2。所以统计一下需要改的位置个数，记为$cnt$.

1.当原字符串为回文串时（$cnt = 0$），那么找到第一个不为'a'的位置和其对称位置，将他们都改成'a'。

2.当不同位置个数为1($cnt = 1$)时，又分为两种情况:

​ 1.可能一个为'a'而一个为非'a'的情况，那么如果此时字符串长度为奇数，那么还可以修改中间位置为'a'!

​ 2.若两个位置都不为'a'，那么就将其全部改为'a'。

3.如果有不同位置的个数为2时($cnt = 2$)，则修改两个位置为两个位置的asc码最小值。

类似题目推荐

塔子哥来推荐几道 字符串 + 贪心 相关的题目给大家训练！

leetcode

1. 680. 验证回文字符串 Ⅱ
2. 1754. 构造字典序最大的合并字符串

CodeFun2000

P1077 美团春招-2023.3.11-第一题-字符串修改

P1101. 阿里-2023.03.21-第二题-最大化01串中1的个数

P1108. 腾讯音乐-2023.3.23-第四题-调整字符串

代码

C++

#include<bits/stdc++.h>
using namespace std;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    int cnt = 0;
    // 遍历字符串，统计需要改变位置的个数
    for (int i = 0; i <= n / 2; i++) {
        if (s[i] != s[n - i - 1]) cnt++;
    }
    if (cnt == 0) { // 原字符串已经是回文串
        for (int i = 0; i < n; i++) {
            if (s[i] != 'a') { // 找到第一个不为'a'的位置和其对称位置并改为'a'
                s[i] = 'a', s[n - i - 1] = 'a';
                break;
            }
        }
    }
    else if (cnt == 1) { // 不同位置的个数为1
        for (int i = 0; i < n; i++) {
            if (s[i] != s[n - i - 1]) {
                if (s[i] == 'a' || s[n - i - 1] == 'a') { // 一个位置为'a'，另一个位置不为'a'
                    if (n % 2) s[n / 2] = 'a'; // 若字符串长度为奇数，修改中间位置为'a'
                }
                s[i] = 'a', s[n - i - 1] = 'a';
            }
        }
    } else { // 不同位置个数为2
        for (int i = 0; i < n; i++) {  // 修改这两个位置为ascii码值较小的字符
            if (s[i] != s[n - i - 1]) s[i] = min(s[i], s[n - i - 1]), s[n - i - 1]   = s[i];
        }
    }
    // 输出修改后的字符串
    cout << s << endl;
}

int main() {
    int t = 1;
    // cin >> t;
    while (t--) solve(); // 处理多组测试数据
    return 0;
}

python

s = list(input())  # 将输入的字符串转化为列表
n = len(s)  # 获取字符串长度
cnt = 0
# 遍历字符串，统计需要改变位置的个数
for i in range(n // 2):
    if s[i] != s[n - i - 1]:
        cnt += 1
if cnt == 0:  # 原字符串已经是回文串
    for i in range(n):
        if s[i] != 'a':  # 找到第一个不为'a'的位置和其对称位置并改为'a'
            s[i] = 'a'
            s[n - i - 1] = 'a'
            break 
elif cnt == 1:  # 不同位置的个数为1
    for i in range(n):
        if s[i] != s[n - i - 1]:
            if s[i] == 'a' or s[n - i - 1] == 'a':  # 一个位置为'a'，另一个位置不为'a'
                if n % 2 == 1:
                    s[n // 2] = 'a'  # 若字符串长度为奇数，修改中间位置为'a'
            s[i] = 'a'
            s[n - i - 1] = 'a'    
else:  # 不同位置个数为2
    for i in range(n):  # 修改这两个位置为ascii码值较小的字符
        if s[i] != s[n - i - 1]:
            s[i] = min(s[i] , s[n - i - 1])
            s[n - i - 1] = s[i]
print("".join(s))  # 将列表转化为字符串并输出

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char[] s = str.toCharArray();  // 将字符串转化为字符数组
        int n = s.length, cnt = 0;
        for (int i = 0; i < n / 2; i++) {  // 遍历一半的字符
            if (s[i] != s[n - i - 1]) {  // 如果对称位置字符不同，则需要改变该字符使其对称
                cnt++;
            }
        }
        if (cnt == 0) {  // 已经是回文串
            for (int i = 0; i < n; i++) {  // 从两端开始寻找第一个字符不是a的位置
                if (s[i] != 'a') {
                    s[i] = 'a';
                    s[n - i - 1] = 'a';  // 改为a
                    break;
                }
            }
        } 
        else if (cnt == 1) {  // 不同的位置只有一个
            for (int i = 0; i < n; i++) {
                if (s[i] != s[n - i - 1]) {
                    if (s[i] == 'a' || s[n - i - 1] == 'a') {  // 一个为'a'，另一个不为'a'
                        if (n % 2 == 1) {  // 字符串长度为奇数，中间位置改为'a'
                            s[n / 2] = 'a';
                        }
                    }
                    s[i] = 'a';
                    s[n - i - 1] = 'a';
                }
            }
        } 
        else {  // 不同的位置有两个
            for (int i = 0; i < n; i++) {  // 修改这两个位置为ascii码值较小的字符
                if (s[i] != s[n - i - 1]) {
                    s[i] = (char) Math.min(s[i], s[n - i - 1]);
                    s[n - i - 1] = s[i];
                }
            }
        }
        System.out.println(String.valueOf(s));  // 将字符数组转化为字符串输出
    }
}

Go

package main
import (
	"fmt"
)
func main() {
	var str string
	fmt.Scan(&str)
	s := []byte(str)  // 将字符串转化为字节数组
	n, cnt := len(s), 0
	for i := 0; i < n/2; i++ {  // 遍历一半的字符
		if s[i] != s[n-i-1] {  // 如果对称位置字符不同，则需要改变该字符使其对称
			cnt++
		}
	}
	if cnt == 0 {  // 已经是回文串
		for i := 0; i < n; i++ {  // 从两端开始寻找第一个字符不是'a'的位置
			if s[i] != 'a' {
				s[i] = 'a'
				s[n-i-1] = 'a'  // 改为'a'
				break
			}
		}
	} else if cnt == 1 {  // 不同的位置只有一个
		for i := 0; i < n; i++ {
			if s[i] != s[n-i-1] {
				if s[i] == 'a' || s[n-i-1] == 'a' {  // 一个为'a'，另一个不为'a'
					if n%2 == 1 {  // 字符串长度为奇数，中间位置改为'a'
						s[n/2] = 'a'
					}
				}
				s[i] = 'a'
				s[n-i-1] = 'a'
			}
		}
	} else {  // 不同的位置有两个
		for i := 0; i < n; i++ {  // 修改这两个位置为ascii码值较小的字符
			if s[i] != s[n-i-1] {
				s[i] = byte(min(int(s[i]), int(s[n-i-1])))
				s[n-i-1] = s[i]
			}
		}
	}
	fmt.Println(string(s))  // 将字节数组转化为字符串输出
}
func min(x, y int) int {  // 返回两个整数中较小的那个
	if x < y {
		return x
	}
	return y
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    const str = lines[0];
    const s = [...str];  // 将字符串转化为字符数组
    const n = s.length;
    let cnt = 0;
    for (let i = 0; i < n/2; i++) {  // 遍历一半的字符
        if (s[i] !== s[n-i-1]) {  // 如果对称位置字符不同，则需要改变该字符使其对称
            cnt++;
        }
    }
    if (cnt === 0) {  // 已经是回文串
        for (let i = 0; i < n; i++) {  // 从两端开始寻找第一个字符不是'a'的位置
            if (s[i] !== 'a') {
                s[i] = 'a';
                s[n-i-1] = 'a';  // 改为'a'
                break;
            }
        }
    } else if (cnt === 1) {  // 不同的位置只有一个
        for (let i = 0; i < n; i++) {
            if (s[i] !== s[n-i-1]) {
                if (s[i] === 'a' || s[n-i-1] === 'a') {  // 一个为'a'，另一个不为'a'
                    if (n%2 === 1) {  // 字符串长度为奇数，中间位置改为'a'
                        s[Math.floor(n/2)] = 'a';
                    }
                }
                s[i] = 'a';
                s[n-i-1] = 'a';
            }
        }
    } else {  // 不同的位置有两个
        for (let i = 0; i < n; i++) {  // 修改这两个位置为ascii码值较小的字符
            if (s[i] !== s[n-i-1]) {
                s[i] = String.fromCharCode(Math.min(s[i].charCodeAt(), s[n-i-1].charCodeAt()));
                s[n-i-1] = s[i];
            }
        }
    }
    console.log(s.join(''));  // 将字符数组转化为字符串输出
});

模板

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    // write your code here
});

题目内容

小美是一个热衷于算法竞赛的程序员，他最近在参加一场名为“回文字符串”的比赛。比赛规则是给定一个字符串，要求将其修改为一个回文字符串，所修改的字符位置最多只能有两个，并且要求修改后的字符串字典序最小。

小美在比赛中遇到了困难，不知道如何处理才能让修改后的字符串达到要求。于是他找到了你，希望你能帮助他解决问题，数据保证能在题目限制下形成回文字符串。

注:回文字符串：即一个字符串从前向后和从后向前是完全一致的字符串。例如字符串$abcba,aaaa,acca$都是回文字符串。字符串$abcd,acea$都不是回文字符串。

输入描述

一行，一个字符串。字符串中仅由小写英文字符构成。

保证字符串不会是空字符串。

字符串长度介于$[1,100000]$ 之间。

输出描述

一行，一个在题目条件限制下所可以获得的字典序最小的回文字符串。

样例$1$

输入

acca

输出

aaaa

说明： 原来的字符串已经是回文字符串了。但它不是题目条件下可以取得的字典序最小的回文字符串。将第二个字符和第三个字符都改为$a$可以获得字典序最小的回文字符串。

样例$2$

输入

abcde

输出

abcba

说明 将$de$改为$ba$可以获得字典序最小的回文字符串。