字串排序（来自蓝桥杯2020省赛 C++ B组 J题：

小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。

在冒泡排序中，每次只能交换相邻的两个元素。小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符，则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。

例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序，总共需要 4 次交换。 小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 V 次交换，可是他忘了把这个字符串记下来，现在找不到了。

请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对该串的字符排序，正好需要 V 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。请注意字符串中可以包含相同的字符。

【输入格式】

输入一行包含一个整数V，为小蓝的幸运数字。 以下N行，包含两个证书 Ai，Bi

【输出格式】

输出一个字符串，为所求的答案。

【样例输入1】

4

【样例输出1】

bbaa

【样例输入2】

100

【样例输出2】

jihgfeeddccbbaa

---

首先蓝桥杯的云课有评测：

https://www.lanqiao.cn/problems/501/learning/

（要先登录）

但是数据水到乱搞过了，连最大的V=10000的评测点都没有，就不用测了 不如直接输入V=100。

---

这题想了接近3h，好几种状态，中间有一个与这篇题解一样的状态和转移：

https://blog.csdn.net/qq_43619717/article/details/112595685

但是里面的状态转移中， k == 1 时，取 j - 1 的最大值，当时无法证明取最大值是正确的。但现在没有评测，没有std所以也没办法判定。bdfs并没有其他的题解了。

如何证明转移是正确的？或者有其他解法吗？

（睡觉起来看看我之前的乱搞解法改了之后对不对）