给出了一个由小写字母组成的字符串 S。然后，我们可以进行任意次数的移动。


在每次移动中，我们选择前 K 个字母中的一个（从左侧开始），将其从原位置移除，并放置在字符串的末尾。


返回我们在任意次数的移动之后可以拥有的按字典顺序排列的最小字符串。


 


示例 1：


输入：S = "cba", K = 1
输出："acb"
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。

示例 2：


输入：S = "baaca", K = 3
输出："aaabc"
解释：
在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。


提示：


1 <= K <= S.length <= 1000

S 只由小写字母组成。


解题思路

1，当 K = 1 时，每次操作只能将第一个字符移动到末尾，因此字符串 S 可以看成一个头尾相连的环。如果 S 的长度为 NN，我们只需要找出这 NN 个位置中字典序最小的字符串即可。

2，当 K = 2 时，可以发现，我们能够交换字符串中任意两个相邻的字母。具体地，设字符串 S 为 S[1], S[2], ..., S[i], S[i + 1], ..., S[N]，我们需要交换 S[i] 和 S[j]。首先我们依次将 S[i] 之前的所有字符依次移到末尾，得到


S[i], S[i + 1], ..., S[N], S[1], S[2], ..., S[i - 1]


随后我们先将 S[i + 1] 移到末尾，再将 S[i] 移到末尾，得到


S[i + 2], ..., S[N], S[1], S[2], ..., S[i - 1], S[i + 1], S[i]


最后将 S[i + 1] 之后的所有字符依次移到末尾，得到


S[1], S[2], ..., S[i - 1], S[i + 1], S[i], S[i + 2], ..., S[N]


这样就交换了 S[i] 和 S[i + 1]，而没有改变其余字符的位置。


3，当 K > 2 时，我们可以完成 K = 2 时的所有操作。

4，上述问题转化成两个子问题

A，K==1 我们从每一个位置剪切然后拼接字符串，求字典序最小的字符串。

B，K>1  当我们可以交换任意两个相邻的字母后，就可以使用冒泡排序的方法，仅通过交换相邻两个字母，使得字符串变得有序。因此当 K >= 2 时，我们可以将字符串移动得到最小的字典序。



代码

func orderlyQueue(S string, K int) string {
    if K==1{
        s:=S
       for i:=0;i<len(S);i++{
          tmp:=S[i:]+S[:i]
          //fmt.Println(s,tmp,large(s,tmp))
          if large(s,tmp){
              s=tmp
          }
       }
       return s
    }
    return sort(S)
}


func sort(s string)string{
   sa:=[]byte(s)
   for i:=0;i<len(s);i++{
       for j:=i;j<len(s);j++{
           if sa[i]>sa[j]{
               sa[i],sa[j]=sa[j],sa[i]
           }
       }
   }
   return string(sa)
}


func large(s1,s2 string)bool{
    for i:=0;i<len(s1);i++{
        if s1[i]>s2[i]{
            return true 
        }
        if s1[i]<s2[i]{
            return false 
        }
    }
    return false
}