Orderly Queue LeetCode Solution

Table of Contents

Problem Statement

Orderly Queue LeetCode Solution – You are given a string s and an integer k. You can choose one of the first k letters of s and append it at the end of the string.

Return the lexicographically smallest string you could have after applying the mentioned step any number of moves.

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".

Explanation

Two possible cases:

K==1,

in this case, by performing given operations we get rotations of the given string. So, the answer would be lexicographically the smallest string among all rotations.

Ex: s=”dcba”

– Remove d from the front and add at back. s=”cbad”.

– Remove c from the front and add at back. s=”badc”

– Remove b from the front and add at back. s=”adcb”

– Remove a from the front and add at back. s=”dcba”

Among all rotated strings, s=”adcb” is lexicographically smallest.

K>=2,

This is an interesting case. Here we are able to swap any elements by performing some number of operations. See below example

Ex: bacd

Let us swap the first two characters i.e. b and a

– Choose a and push to the back. s=”bcda”

– Choose b and push to the back. s=”cdab”

– Choose c and push to the back. s=”dabc”

– Choose d and push to the back. s=”abcd”

We can observe that the first two letters of bacd are swapped now abcd. Since we can swap any two elements this implies it is possible to sort an entire string just apply some number of operations. Hence, in this case, the answer would be sorted string.

First, this is string rotation.
12345 -> 23451 -> 34512 -> 45123 -> 51234 ( Used numbers instead of letters to make it clear. )

If K == 1, we can only rotate the whole string. There are S.length different states and we return the lexicographically smallest string.

If K > 1, it means we can:

rotate the whole string,
rotate the whole string except the first letter.
012345 -> 023451 -> 034512 -> 045123 -> 051234

We can rotate i+1th big letter to the start (method 1),
then rotate ith big letter to the end (method 2).
2XXX01 -> XXX012

In this way, we can bubble sort the whole string lexicographically.
So just return the sorted string.

Code

C++ Code for Orderly Queue

class Solution {
public:
    string orderlyQueue(string S, int K) {
        if (K > 1) {
            sort(S.begin(), S.end());
            return S;
        }
        string res = S;
        for (int i = 1; i < S.length(); i++)
            res = min(res, S.substr(i) + S.substr(0, i));
        return res;
    }
};

Java Code for Orderly Queue

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

Python Code for Orderly Queue

class Solution:
    def orderlyQueue(self, S, K):
        return "".join(sorted(S)) if K > 1 else min(S[i:] + S[:i] for i in range(len(S)))