LeetCode 899. Ordered Queues

题目描述

给定一个字符串 s 和一个整数 k .你可以从 s 的前 k 个字母中选择一个,并把它加到字符串的末尾.

返回 在应用上述步骤的任意数量的移动后,字典上最小的字符串 .

思路

It was relatively simple at first,从前k个位置中,Just keep moving the first character of the reversed pair to the last position.

So you will see such a use case：

“baaca”

2

Use the above strategy,得到的答案是：aacab,The actual answer is yesaaabc.

容易发现,当k >= 2 时,The original string can be converted,Perform arbitrary transformations,That is to say, you can get any string,Then, of course, you can also get the string with the smallest lexicographical order.

在k = 2时,我们可以交换字符串中的Any two adjacent characters,and leave the rest of the characters unchanged

比如原字符串为1234ab56789,We want to exchangeab

Then you can continuously move the first character to the end,直到abappears in the first

ab567891234

随后我们将a移到末尾,得到b567891234a

接着,将bThe last bit is constantly swapped to the end（使得a不断往前走）,得到ba567891234

再将baRotate to the original position（Keep moving the first character to the end）,得到1234ba56789

This achieves the exchangeab两个字符.

同理,We can keep the rest of the characters in the same position,Swap any two other adjacent characters.

As long as we can swap any two adjacent characters,Bubble sort can be achieved.

于是,在k = 2时,We always get sorted strings,That is, the string with the smallest lexicographical order is always obtained.

对于k > 2,就更不用说了.

而在k = 1时,We can only swap the first character to the end at a time,A string that can be constructed,一共只有n种情况（n是字符串的长度,Every character can act as the first character,所以共n种）.

代码

The idea came up,The code is very easy to write.The difficulty is in thinking.

We just need to categorize and discuss,k = 1时,Rotate the entire string,Find the one with the smallest lexicographical order;k >= 2时,Sort the strings lexicographically.

class Solution {
    
    public String orderlyQueue(String s, int k) {
    
        int n = s.length();
        if (k == 1) {
    
            String ans = s;
            for (int i = 0; i < n; i++) {
    
                s = s.substring(1) + s.charAt(0);
                if (ans.compareTo(s) > 0) ans = s;
            }
            return ans;
        }
        // k = 2
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }
}

时间复杂度 ：$O(n^2)$

• 在k = 1need to enumeraten个可能的字符串,And the comparison of each string is required$O(n)$的时间,所以一共是$O(n^2)$.当然,这个过程可以使用字符串的最小表示法,优化到$O(n)$
• 在k >= 2need to be sorted,复杂度$O(nlogn)$,最坏$O(n^2)$

空间复杂度：$O(n)$

在k = 1need to open up additional space to store all possible strings（因为JavaStrings in are immutable objects）

扩展

字符串的最小表示法：Find the smallest lexicographical order that can be obtained by rotating a string

TODO