0899. Orderly Queue¶
题目信息¶
- 题号:
0899
- 难度:
Hard
- 主题:
字符串、队列操作、字典序
- 原题:
- 重点:
每次只能从当前字符串前 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。该结果已经是所有字符按升序排列的字符串,不可能存在字典序更小的排列。