2022.08.03_Daily Question

899. 有序队列

题目描述

给定一个字符串 s 和一个整数 k .你可以从 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 只由小写字母组成.

coding

class Solution {
    
    public String orderlyQueue(String s, int k) {
    
        if (k == 1) {
    
            // 当 k == 1 时, Only loops are possible n 次, Every move will s.charAt(0) 移动到 s.charAt(s.length() - 1)
            // Think of it as a circular queue, Its own alphabetical order does not change
            // We just need to simulate it, 找出 s can be the minimum
            StringBuilder str = new StringBuilder(s);
            for (int i = 0; i < s.length(); i++) {
    
                char temp = str.charAt(0);
                str.deleteCharAt(0);
                str.append(temp);
                s = s.compareTo(str.toString()) > 0 ? str.toString() : s;
            }
            return s;
        } else {
    
            // 当 k > 1 时, it may first 0 characters move, Possibly too 1 characters move, ...第 k -1 characters to move
            // If you think of it as a circular array, Its adjacent characters are interchangeable, So that any two characters can eventually be exchanged 
            // 比如: 
            // eg1 :
            // s : "cba"
            // k : 2
            // -> b 移动 : "cab"
            // -> c 移动 : "abc"
            //
            // eg2 :
            // s : "cbad"
            // k : 2
            // -> b 移动 : "cadb"
            // -> c 移动 : "adbc"
            // -> d 移动 : "abcd"
            // 从而做到 s 的全排列
            // (PS:The order can be changed at will, It must be possible to achieve full permutation of strings)
            // At this point the topic has changed, 一个字符串, 经过 n 多次移动, What is the final minimum string, 直接 Arrays.sort() 即可 
            char[] chs = s.toCharArray();
            Arrays.sort(chs);
            return new String(chs);
        }
    }
}