Problem
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 <= 1000Sconsists of lowercase letters only.
Solution: Rotation or Sort?
if \(k =1\), we can only rotate the string.
if \(k > 1\), we can bubble sort the string.
Time complexity: O(n^2)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 4 ms class Solution { public: string orderlyQueue(string S, int K) { if (K > 1) { sort(begin(S), end(S)); return S; } string ans = S; for (int i = 1; i < S.size(); ++i) ans = min(ans, S.substr(i) + S.substr(0, i)); return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public String orderlyQueue(String S, int K) { if (K > 1) { char[] chars = S.toCharArray(); Arrays.sort(chars); return new String(chars); } String ans = S; for (int i = 1; i < S.length(); ++i) { String tmp = S.substring(i) + S.substring(0, i); if (tmp.compareTo(ans) < 0) ans = tmp; } return ans; } } |
Python3 SC O(n^2)
|
1 2 3 4 5 |
# Author: Huahua 48 ms class Solution: def orderlyQueue(self, S, K): if K > 1: return ''.join(sorted(S)) return min([S[i:] + S[0:i] for i in range(0, len(S))]) |
Python3 SC O(n)
|
1 2 3 4 5 6 7 8 |
# Author: Huahua 36 ms class Solution: def orderlyQueue(self, S, K): if K > 1: return ''.join(sorted(S)) ans = S for i in range(0, len(S)): ans = min(ans, S[i:] + S[0:i]) return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment