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.