899. ordered queue

Preface

C++ It's a high-level programming language , from C Language expansion and upgrading , As early as 1979 By Benjani · Strauss LUP is AT&T Developed by Bell studio .
C++ Both can be carried out C Process programming of language , It can also be used for object-based programming characterized by abstract data types , It can also carry out object-oriented programming characterized by inheritance and polymorphism .C++ Good at object-oriented programming at the same time , You can also do process based programming .
C++ Have the practical characteristics of computer operation , At the same time, it is also committed to improving the programming quality of large-scale programs and the problem description ability of programming languages .

Java Is an object-oriented programming language , Not only absorbed C++ The advantages of language , It's abandoned C++ The incomprehensible inheritance in 、 Concepts such as pointer , therefore Java Language has two characteristics: powerful and easy to use .Java As the representative of static object-oriented programming language , Excellent implementation of object-oriented theory , Allow programmers to do complex programming in an elegant way of thinking .
Java It's simple 、 object-oriented 、 Distributed 、 Robustness, 、 Security 、 Platform independence and portability 、 Multithreading 、 Dynamic and so on .Java Can write desktop applications 、Web Applications 、 Distributed system and embedded system applications, etc .

Python By Guido of the Dutch Society for mathematical and computer science research · Van rosum On 1990 It was designed in the early 's , As a course called ABC A substitute for language .Python Provides efficient advanced data structure , It's also a simple and effective way of object-oriented programming .Python Syntax and dynamic types , And the nature of interpretative language , Make it a programming language for scripting and rapid application development on most platforms , With the continuous update of the version and the addition of new language features , Gradually used for independent 、 Development of large projects .
Python The interpreter is easy to extend , have access to C Language or C++（ Or something else can be done through C Calling language ） Expand new functions and data types .Python It can also be used as an extensible programming language in customizable software .Python Rich library of standards , Provides source code or machine code for each major system platform .
2021 year 10 month , Compiler for language popularity index Tiobe take Python Crowned the most popular programming language ,20 Put it in... For the first time in years Java、C and JavaScript above .

describe

Given a string s And an integer k . You can start your s Before k Select one of the letters , And add it to the end of the string .

return After applying any number of movements of the above steps , The smallest string in the dictionary .

Example 1：

Input ：s = "cba", k = 1
Output ："acb"
explain ：
In the first step , We'll take the first character （“c”） Move to the end , Get string “bac”.
In the second step , We'll take the first character （“b”） Move to the end , Get the final result “acb”.

Example 2：

Input ：s = "baaca", k = 3
Output ："aaabc"
explain ：
In the first step , We'll take the first character （“b”） Move to the end , Get string “aacab”.
In the second step , We'll take the third character （“c”） Move to the end , Get the final result “aaabc”.

Tips ：

    1 <= k <= S.length <= 1000
    s It's just small letters .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/orderly-queue
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1 ： mathematics

When K = 1 when , Each operation can only move the first character to the end , So strings S It can be seen as a ring connected from head to tail . If S The length of is NNN, We just need to find out NNN The string with the smallest lexicographic order among the positions is sufficient .

When K = 2 when , You can find , We can exchange any two adjacent letters in a string . In particular , Set string S by S[1], S[2], ..., S[i], S[i + 1], ..., S[N], We need to exchange S[i] and S[j]. First of all, let's put S[i] All previous characters are moved to the end in turn , obtain

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

Then we will S[i + 1] Move to end , then S[i] Move to end , obtain

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

The final will be S[i + 1] All subsequent characters are moved to the end in turn , obtain

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

This is the exchange S[i] and S[i + 1], Without changing the position of the rest of the characters .

When we can exchange any two adjacent letters , You can use the bubble sort method , Only by exchanging two adjacent letters , Make the string orderly . So when K = 2 when , We can move the string to get the smallest dictionary order .

When K > 2 when , We can finish K = 2 All of the operations when .

author ：LeetCode
link ：https://leetcode.cn/problems/orderly-queue/solution/you-xu-dui-lie-by-leetcode/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

class Solution {
    public String orderlyQueue(String S, int K) {
        if (K == 1) {
            String ans = S;
            for (int i = 0; i < S.length(); ++i) {
                String T = S.substring(i) + S.substring(0, i);
                if (T.compareTo(ans) < 0) ans = T;
            }
            return ans;
        } else {
            char[] ca = S.toCharArray();
            Arrays.sort(ca);
            return new String(ca);
        }
    }
}


 author ：LeetCode
 link ：https://leetcode.cn/problems/orderly-queue/solution/you-xu-dui-lie-by-leetcode/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .