Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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

Solution

Method 1 – Rotation and Sorting

Intuition

If k == 1, we can only rotate the string by moving the first character to the end, so we must try all rotations and pick the smallest. If k > 1, we can rearrange the string in any order by repeatedly moving any of the first k characters to the end, so the answer is the sorted string.

Approach

  1. Check value of k:
    • If k == 1, generate all rotations of the string and return the lexicographically smallest.
    • If k > 1, sort the string and return it.
  2. For k == 1:
    • For each index i in the string, rotate the string by moving the first i characters to the end.
    • Track the smallest string found.
  3. For k > 1:
    • Convert the string to a list/array of characters.
    • Sort the characters.
    • Return the sorted string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
	 string orderlyQueue(string s, int k) {
		  if (k == 1) {
				string ans = s;
				int n = s.size();
				for (int i = 1; i < n; ++i) {
					 string rotated = s.substr(i) + s.substr(0, i);
					 if (rotated < ans) ans = rotated;
				}
				return ans;
		  }
		  string ans = s;
		  sort(ans.begin(), ans.end());
		  return ans;
	 }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
	 public String orderlyQueue(String s, int k) {
		  if (k == 1) {
				String ans = s;
				int n = s.length();
				for (int i = 1; i < n; ++i) {
					 String rotated = s.substring(i) + s.substring(0, i);
					 if (rotated.compareTo(ans) < 0) ans = rotated;
				}
				return ans;
		  }
		  char[] arr = s.toCharArray();
		  Arrays.sort(arr);
		  return new String(arr);
	 }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
	 def orderlyQueue(self, s: str, k: int) -> str:
		  if k == 1:
				ans: str = s
				for i in range(1, len(s)):
					 rotated: str = s[i:] + s[:i]
					 if rotated < ans:
						  ans = rotated
				return ans
		  return ''.join(sorted(s))

Complexity

  • Time: O(N^2) for k == 1 (all rotations), O(N log N) for k > 1 (sorting)
  • Space: O(N) for storing rotations or sorted string