0899. Orderly Queue

题目信息

题号:

0899

难度:

Hard

主题:

字符串、队列操作、字典序

原题:

LeetCode 0899

重点:

每次只能从当前字符串前 k 个字符中选一个移到末尾;可执行任意次数,返回所有可达字符串中字典序最小者

题目重述

给定小写字符串 s 和整数 k。一次操作可以从当前字符串的前 k 个字符中选择任意一个,把它从原位置删除并追加到字符串末尾,其余字符保持相对顺序。

可以执行任意次数操作,也可以一次都不执行。请返回通过这些操作能够得到的字典序最小字符串。每一步可选范围都根据操作后的当前字符串重新确定。

1 <= k <= s.length <= 1000,s 只包含小写英文字母。

自建示例

只能移动首字符时比较全部循环旋转:

输入:s = "baca", k = 1
输出:"abac"
解释:可达的循环旋转为 baca、acab、caba 和 abac,其中字典序最小的是 abac。

前两个字符可选时能够得到完整排序结果:

输入:s = "caba", k = 2
输出:"aabc"
解释:可以依次选择当前第二个字符,得到 cbaa;再次选择第二个字符,得到 caab;最后选择第一个字符,得到 aabc。该结果已经是所有字符按升序排列的字符串,不可能存在字典序更小的排列。