LeetCode: 899. Orderly Queue

题目描述

A string S of lowercase letters is given. Then, we may make any number of moves.
In each move, we choose one of the first K letters (starting from the left), remove it, and place it at the end of the string.
Return the lexicographically smallest string we could have after any number of moves.

Example 1:

Input: S = "cba", K = 1
Output: "acb"
Explanation: 
In the first move, we move the 1st character ("c") to the end, obtaining the string "bac".
In the second move, we move the 1st character ("b") to the end, obtaining the final result "acb".

Example 2:

Input: S = "baaca", K = 3
Output: "aaabc"
Explanation: 
In the first move, we move the 1st character ("b") to the end, obtaining the string "aacab".
In the second move, we move the 3rd character ("c") to the end, obtaining the final result "aaabc".

Note:

1 <= K <= S.length <= 1000
S consists of lowercase letters only.

解题思路

  1. 当 K == 1 时， 只能循环移动每个元素，无法改变相对位置。因此只需要获取循环移动过程中字典序最小的序列。
  2. 当 K > 1 时， 可以生成当前字符串的任意序列。因此将原字符串排序生成字典序最小的序列。

AC 代码

class Solution {
public:
    string orderlyQueue(string S, int K) {
        if(K == 1) // 当 K == 1 时， 只能循环移动每个元素。无法改变相对位置。
        {
            string minStr = S;
            for(int i = 1; i < S.size(); ++i)
            {
                S = S.back() + S.substr(0, S.size()-1);
                if(S < minStr) minStr = S;
            }

            return minStr;
        }
        else // 当 K > 1 时， 可以生成当前字符串的任意序列。
        {
            sort(S.begin(), S.end());
            return S;
        }
    }
};