字符串变换最小字符串（C语言）

题目描述

给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）。

变换规则：交换字符串中任意两个不同位置的字符。

输入描述

一串小写字母组成的字符串s

输出描述

按照要求进行变换得到的最小字符串。

用例

备注

s是都是小写字符组成

1<=s.length<=1000

代码

// 引入必要的头文件，用于输入输出和字符串操作
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义一个常量，表示字符串的最大长度
#define MAX_LEN 1000

// 自定义比较函数cmp，用于qsort对字符数组进行字典序排序
int cmp(const void *a, const void *b) {
   
    // 返回两个字符的ASCII码之差，使得字符按字典序排列
    return *(char *)a - *(char *)b;
}

int main() {
   
    // 定义原始字符串s，并读取用户输入的字符串内容
    char s[MAX_LEN];
    scanf("%s", s);

    // 计算字符串s的长度
    int len = strlen(s);

    // 创建一个新的字符数组sorted_s，用于存储原始字符串s排序后的副本
    char sorted_s[MAX_LEN];
    strcpy(sorted_s, s);

    // 使用qsort对sorted_s进行升序排序
    qsort(sorted_s, len, sizeof(char), cmp);

    // 比较排序后与原始字符串，如果相同则无需交换，直接输出原始字符串并返回
    if (strcmp(sorted_s, s) == 0) {
   
        printf("%s", s);
        return 0;
    }

    // 遍历原始字符串，寻找第一个未在正确位置上的字符
    for (int i = 0; i < len; i++) {
   
        if (s[i] != sorted_s[i]) {
   
            // 找到该字符在排序后字符串中的正确位置（索引）
            int index;
            for (int j = 0; j < len; j++) {
   
                if (sorted_s[i] == s[j]) {
   
                    index = j;
                    //注意：这里没有加break;
                    //s:afcdbb, sorted_s:abbcdf,index应该是最后一个b的位置，这样s变成abcdbf而不是abcdfb,abcdbf的字典序比abcdfb小
                }
            }

            // 交换原始字符串中找到的错误字符与其正确位置上的字符
            char tmp = s[i];
            s[i] = sorted_s[i];
            s[index] = tmp;

            // 由于我们只允许一次交换，所以找到一对字符后就可以结束循环
            break;
        }
    }

    // 输出经过变换后得到的最小字符串
    printf("%s\n", s);

    // 主函数返回0表示程序正常执行完毕
    return 0;
}

注意;

“最小字典序字符串”是什么意思?

“最小字典序字符串”是指在一个给定的字符集合中，按照特定排序规则（通常是字母表顺序或数字大小顺序）排列起来形成的字符串中，排在最前面的那个字符串。在计算机科学和数学中，这种排序规则通常基于ASCII码或者Unicode编码的值。

对于由小写字母组成的字符串而言，最小字典序字符串意味着字母按照英文字母表从前往后依次排列。例如，在所有可能的6个字符长度的字符串中，“abcdef”是比“abcdeg”、“abcfed”等其他字符串字典序更小的字符串，因为它的每个字符都在字母表上位置靠前。

当题目要求求解一个字符串变换后的最小字典序字符串时，目标是通过允许的操作（如交换字符、删除字符等）使得最终得到的字符串在其所有可能变化形式中处于字典序排序上的最前端。

为什么“遍历原始字符串，寻找第一个未在正确位置上的字符；交换原始字符串中找到的错误字符与其正确位置上的字符”就可以求出“最小字典序字符串”

在给定的变换规则下，要通过一次交换操作使字符串变为字典序最小，我们需要找到的是这样一对字符：其中一个字符原本位于它应该在排序后出现的位置之前，并且这个字符与它后面应当出现在该位置上的字符进行交换。

例如，如果字符串是 “bcdefa”，按照字典序排列应该是 “abcdef”。那么，我们发现 ‘a’ 字符在原始字符串中的位置（索引为 5）比它在排序后的正确位置（索引为 0）靠后。因此，将 ‘a’ 与它前面的一个字符（这里是 ‘b’）交换位置，得到 “acdefb”，此时字符串变成了字典序上可能的最小值。

这个策略的核心在于：

1. 字典序最小意味着所有字符都应该尽可能地向左移动。
2. 因此，我们应该优先考虑那些位于排序后对应位置之后的字符，并将其与当前所在位置之前的字符交换，以使其移动到更靠前的位置。

代码中通过遍历原字符串并比较其与已排序字符串对应位置的字符来定位需要交换的一对字符，一旦找到这样的字符对就立即进行交换，并且由于题目只允许一次交换，所以在完成首次交换后就会结束循环。这样处理的结果就是得到了字典序上仅通过一次交换能得到的最小字符串。