Leetcode 899. Orderly Queue
Problem Explanation
The problem is about re-arranging characters in a string. We start with a string of lowercase letters, and we have to make moves to re-arrange this string. In each move, we can only pick one of the first K letters in the string (from left or beginning of the string), remove it, and place it at the end of the string. The goal is to make strategic moves, so the final string that we end up with is the smallest string lexicographically.
Let's take an example:
Consider a string S="cba"
and K=1
. In the first move, if we pick the 1st character "c" and move it to the end, the string becomes "bac". In the second move, we again pick the 1st character "b" and move it to the end, our string now becomes "acb". We cannot make any further advantageous moves, and hence the smallest string we can get is "acb".
Solution Approach
In the solution, if K>1, we simply sort the string. Since if K>1, we can essentially move any two letters. Therefore, the smallest string in this case would be the sorted string.
When K=1, the approach is different. The idea is to make moves such that the smallest character among the first K characters is always the first character of the string. We only move the smallest character to the end. This way, we ensure that the first character is always the smallest which will help achieve the lexicographically smallest string.
To implement this, we iterate over the length of the string. In each iteration, we form a new string that starts with character s[i]
followed by all characters before it. Then we compare this new string with the current smallest. If it's smaller, we update the smallest. At the end of the iteration, we return the smallest.
Python Solution
1 2python 3class Solution: 4 def orderlyQueue(self, s: str, k: int) -> str: 5 if k > 1: # if K>1, then we just sort the string 6 return ''.join(sorted(s)) 7 else: # if K=1, then we revolve the string and find the lexicographically smallest 8 return min(s[i:] + s[:i] for i in range(len(s)))
Java Solution
1 2java 3public class Solution { 4 public String orderlyQueue(String s, int k) { 5 if (k > 1) { 6 char[] c = s.toCharArray(); 7 Arrays.sort(c); 8 return new String(c); 9 } 10 String res = s; 11 for (int i = 1; i < s.length(); i++) { 12 String temp = s.substring(i) + s.substring(0, i); 13 if (res.compareTo(temp) > 0) 14 res = temp; 15 } 16 return res; 17 } 18}
Javascript Solution
1 2javascript 3class Solution { 4 orderlyQueue(s, k) { 5 if (k > 1) { 6 return s.split('').sort().join(''); 7 } 8 let res = s; 9 for (let i = 1; i < s.length; i++) { 10 let temp = s.slice(i) + s.slice(0, i); 11 if (res.localeCompare(temp) > 0) 12 res = temp; 13 } 14 return res; 15 } 16}
C++ Solution
1 2cpp 3class Solution { 4public: 5 string orderlyQueue(string s, int k) { 6 if (k > 1) { 7 sort(s.begin(), s.end()); 8 return s; 9 } 10 string res = s; 11 for (int i = 1; i < s.size(); i++) { 12 string temp = s.substr(i) + s.substr(0, i); 13 if (res.compare(temp) > 0) 14 res = temp; 15 } 16 return res; 17 } 18};
C# Solution
1
2csharp
3public class Solution {
4 public string OrderlyQueue(string s, int k) {
5 if (k > 1) {
6 return string.Concat(s.OrderBy(c => c));
7 }
8 string res = s;
9 for (int i = 1; i < s.Length; i++) {
10 string temp = s.Substring(i) + s.Substring(0, i);
11 if (string.Compare(res, temp) > 0)
12 res = temp;
13 }
14 return res;
15 }
16}
Golang Solution
While Go is a statically typed, compiled language like C++, it also includes garbage collection and type safety like Java. Hence, writing a solution in Go gives us the speed of C++ and the ease of coding of Java. Here's how the solution would look like in Go:
1 2go 3package main 4 5import ( 6 "sort" 7 "strings" 8) 9 10func orderlyQueue(s string, k int) string { 11 if k > 1 { 12 sArr := strings.Split(s, "") 13 sort.Strings(sArr) 14 return strings.Join(sArr, "") 15 } 16 res := s 17 for i := 1; i < len(s); i++ { 18 tmp := s[i:] + s[:i] 19 if tmp < res { 20 res = tmp 21 } 22 } 23 return res 24}
Swift Solution
Swift is a powerful and intuitive programming language for macOS, iOS, watchOS, and tvOS, developed by Apple. Writing a solution for the given problem in Swift emphasizes its ease of use and similarity to English.
1
2swift
3class Solution {
4 func orderlyQueue(_ s: String, _ k: Int) -> String {
5 var sArr = Array(s)
6 if k > 1 {
7 sArr.sort()
8 return String(sArr)
9 }
10 var res = s
11 for i in 0..<sArr.count {
12 let tmp = String(sArr[i...] + sArr[0..<i])
13 res = tmp < res ? tmp : res
14 }
15 return res
16 }
17}
Ruby Solution
Unlike Java or C++, Ruby is a scripting language. So, when you want to solve problems English like expressive language, you can give Ruby a try.
1 2ruby 3class Solution 4 def orderly_queue(s, k) 5 if k > 1 6 return s.chars.sort.join 7 end 8 res = s 9 for i in 1...s.length 10 tmp = s[i, s.length-i] + s[0, i] 11 res = [res, tmp].min 12 end 13 return res 14 end 15end
In the solutions above, most of them follow the same approach as mentioned in the problem explanation. The language choice depends on your comfort, the available resources and the performance you need for your application.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.