899. Orderly Queue

Orderly Queue

Problem Description

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

Return the lexicographically smallest string you could have after applying the mentioned step to 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".

 

Constraints:

• 1 <= k <= s.length <= 1000
• s consist of lowercase English letters.

Approach) Sorting

In fact when K > 1 we can totally sort the string.

By swapping two neighbors, we can sort a string -- this is how bubble sorting works.
And by choosing one of two neighbors and placing it at the end, we can rearrange/swap these two elements -- therefore we can sort the string when K>=2.

So the only part we need to deal with is when K===1.

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var orderlyQueue = function(S, K) {
    if(K>1) return S.split('').sort().join('');
    else{
    	let small = S.split('').sort()[0];
    	let ops = [];
    	for(let i=0; i<S.length; i++){
    		if(S[i]===small) ops.push(S.slice(i)+S.slice(0,i));
    	}
    	return ops.sort()[0];
    }
};

Approach) One Liner

The solution itself is easy, if 1 < k - sorted, otherwise rotate s s.length times and pick the lexicographically smallest one.

const orderlyQueue = (s, k) => 1 < k ? [...s].sort().join('') : Array.from({ length: s.length }, (_, i) => i).reduce((a, x) => (s.slice(x) + s.slice(0, x) < a ? s.slice(x) + s.slice(0, x) : a), s);

Approach) Another Native Solution

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var orderlyQueue = function(s, k) {
    if(k === 1){
       let ans = s;
        
       for(let i=0;i<s.length;i++){
             const compareString = s.substr(i)+s.substr(0,i);
			
			// localcompare string using localeCompare() method - javascript
             if(ans.localeCompare(compareString) > 0){
                 ans = s.substr(i)+s.substr(0,i);
             }
      }
        
      return ans;
    }
	
	// if k > 1
   return s.split('').sort().join('');
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #899. Orderly Queue

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!