题目描述

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

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

思路：贪心

由于题目中说了最多只能交换一次，也就是可以不交换或者交换一次，从贪心的角度，那么一定选择字符串中最小的那一个字符作为整个字符串靠前的字符更优，如果出现多个相同的最小字符，那么显然应该选择最靠近字符串末尾的那一个。证明如下：

假设一个字符串，最小的字符用$*$表示，非最小的字符用$@$表示，假设一个字符串可以写成如下形式：$@@*@@*$，那么可以枚举交换策略，如下：

源串： $@@*@@*$

策略一：$*@@@@*$