E卷-(100分)字符串变换最小字符串

字符串变换最小字符串

问题描述

给定一个由小写字母组成的字符串 ，你可以最多进行一次变换操作。变换操作的规则是：交换字符串中任意两个不同位置的字符。请返回经过变换后能得到的字典序最小的字符串。

输入格式

输入一行，包含一个由小写字母组成的字符串 。

输出格式

输出一行，表示经过最多一次变换后得到的字典序最小的字符串。

样例输入

abcdef

样例输出

abcdef

样例解释

字符串 "abcdef" 已经是字典序最小的，不需要进行任何交换操作。

样例输入

bcdefa

样例输出

acdefb

样例解释

将 'a' 和 'b' 交换位置，可以得到字典序最小的字符串 "acdefb"。

数据范围

• 字符串 仅由小写字母组成。
• ，其中 表示字符串 的长度。

题解

这道题目的核心思想是找到字符串中第一个不在正确位置上的字符，然后将它与后面最小的字符交换。

具体步骤如下：

1. 首先，将输入的字符串 排序，得到一个新的字符串 。这个排序后的字符串就是理论上能得到的字典序最小的字符串。

2. 比较原字符串 和排序后的字符串 。如果它们相同，说明原字符串已经是字典序最小的，直接返回原字符串。

3. 如果不同，那么我们需要进行一次交换操作。从左到右遍历原字符串 ，找到第一个与 中对应位置不同的字符。

4. 在原字符串 中，从右向左找到与这个字符相等的字符（即 中对应位置的字符）。

5. 交换这两个字符的位置。

参考代码

• Python

def solve(s):
    # 将输入字符串转换为列表，方便操作
    s_list = list(s)
    # 对字符串进行排序，得到理论上的最小字符串
    sorted_s = sorted(s)
    
    # 如果原字符串已经是最小的，直接返回
    if s_list == sorted_s:
        return s
    
    # 找到第一个不在正确位置的字符
    for i in range(len(s)):
        if s_list[i] != sorted_s[i]:
            # 从右向左找到要交换的字符
            j = s.rindex(sorted_s[i])
            # 交换字符
            s_list[i], s_list[j] = s_list[j], s_list[i]
            break
    
    # 将列表转换回字符串并返回
    return ''.join(s_list)

# 读取输入
s = input().strip()

# 输出结果
print(solve(s))

• C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LEN 1001

// 比较函数，用于qsort
int cmp(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}

// 解决问题的函数
void solve(char *s) {
    int len = strlen(s);
    char sorted_s[MAX_LEN];
    strcpy(sorted_s, s);
    
    // 对sorted_s进行排序
    qsort(sorted_s, len, sizeof(char), cmp);
    
    // 如果原字符串已经是最小的，直接返回
    if (strcmp(s, sorted_s) == 0) {
        return;
    }
    
    // 找到第一个不在正确位置的字符
    for (int i = 0; i < len; i++) {
        if (s[i] != sorted_s[i]) {
            // 从右向左找到要交换的字符
            int j;
            for (j = len - 1; j > i; j--) {
                if (s[j] == sorted_s[i]) {
                    break;
                }
            }
            //