字典序最小回文构造

问题描述

小R手中有一个由小写英文字母组成的字符串。她希望将这个字符串转换为回文字符串，并且要求字典序尽可能小。在这个过程中，小R最多可以更改字符串中的两个字符。每个字符可以被更改为任意的小写字母。现在你的任务是帮助小R构造出在满足条件的前提下字典序最小的回文字符串。

例如：对于字符串 acca，通过更改两个字符，可以得到回文字符串 aaaa，这是字典序最小的解。

解题思路

本题核心是在限定的操作次数内（最多两次），将给定字符串转换为字典序最小的回文串，需要考虑：

  1. 优先保证回文性： 首先需要通过替换操作使其变为回文串。
  2. 字典序最小化： 在保证回文性的基础上，尽可能将字符串的字典序最小化，可将字符替换为 a 保证最小。
  3. 操作次数限制： 操作次数不能超过两次，并且尽可能一次替换影响两个对称位置的字符，最后再考虑奇数长度字符串。

具体步骤：

  • 步骤1：构造回文串
    从字符串的两端向中间遍历，比较对称位置的字符：
    • 如果字符相同，无需操作。
    • 如果字符不相同，需要进行替换，取两者中较小一个，计数一次操作。
  • 步骤2：字典序最小化
    再次从字符串的两端向中间遍历：
    • 如果当前字符不是 a，且还有操作次数剩余，则将对称位置的字符同时替换为 a，这样一次操作能影响两个字符。
    • 如果字符串长度为奇数，且中间字符不是 a，且还有操作次数剩余，则将中间字符替换为 a。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;

string solution(string s)
{
    int n = s.length();
    int changes = 0;

    // 检查是否回文串，如果不是，尽量变成回文串
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - 1 - i]) {
            changes++;
            if (s[i] < s[n - 1 - i])
                s[n - 1 - i] = s[i];
            else
                s[i] = s[n - 1 - i];
        }
    }

    // 如果修改次数没超过 2 次，尽量改成a
    for (int i = 0; i < n / 2 && changes < 2; i++)
        if (s[i] != 'a' && changes < 1) { // 如果没修改过，一次性修改两个字符
            s[i] = 'a';
            s[n - 1 - i] = 'a';
            changes += 2;
        }

    // 如果是奇数长度，且次数还没用完，中间字符改成a
    if (n % 2 == 1 && changes < 2)
        s[n / 2] = 'a';

    return s;
}

int main()

{
    cout << (solution("acca") == "aaaa") << endl;
    cout << (solution("racecar") == "aacecaa") << endl;
    cout << (solution("fecdef") == "feccef") << endl;
    return 0;
}

代码解析

  1. 构造回文串：
    • 遍历字符串的前一半，与后一半的对称位置比较。
    • 如果字符不相同，选择较小的字符进行替换，确保回文性的同时使字典序尽可能小。
    • 每次替换操作计数 changes 加一。
  2. 字典序最小化：
    • 在保证回文性的基础上，再次遍历字符串的前一半。
    • 如果当前位置的字符不是 a，且剩余的操作次数允许，则将对称位置的字符同时替换为 a。
    • 每次这样的双字符替换操作计数 changes 加二。
  3. 处理中间字符：
    • 如果字符串长度为奇数，且还有剩余的操作次数，检查中间的字符。
    • 如果中间字符不是 a，则将其替换为 a，计数 changes 加一。

知识点总结

  • 字符串操作： 熟练使用字符串的索引操作，访问和修改字符串中的字符。
  • 双指针技巧： 在字符串处理中，常使用双指针从两端向中间遍历，用于处理回文串等对称结构的问题。
  • 贪心策略： 在每一步选择中，做出当前最优的选择。为了保证回文且字典序最小，优先将字符替换为两者较小的一个，再替换为 a。

总结

通过这道题，学习了如何在有限的操作次数内，将字符串转换为字典序最小的回文串。核心在于结合回文串的特性和贪心策略，合理安排替换操作，使得在满足条件的前提下，得到最优解。该题还强化了我对字符串处理、双指针遍历以及算法优化的理解和应用。