899. Orderly Queue

HardMathStringSorting
Leetcode Link

Problem Description

You are provided with two inputs: a string s and an integer k. The task is to form the lexicographically smallest string possible by repeatedly performing the following operation: choose one of the first k letters from the string s, and append it to the end of the same string. This operation can be performed as many times as you wish.

Intuition

To solve this problem, we look at two separate cases based on the value of k:

  • Case where k is equal to 1: The only operation allowed in this case is to take the first character of the string and append it to the end. To find the lexicographically smallest string, we can simulate this operation for each character in the string. By doing this, we try all possible rotations of the string to find the smallest one.

  • Case where k is greater than 1: When k is greater than 1, it means we have the ability to move not just the first character but any of the first k characters to the end. This effectively allows us to sort the string to achieve the lexicographically smallest string possible. The reasoning is that we can move the smallest character in the first k characters to the front, followed by the next smallest, forming an increasing sequence, which is the definition of a sorted string.

Thus, our solution approach is:

  1. If k is 1, we simulate rotating the string and keep track of the smallest string seen so far, and then return that string.
  2. If k is greater than 1, we simply return the sorted string.

Learn more about Math and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The solution follows a straightforward approach that depends on whether k equals 1 or is greater than 1. Let's discuss the implementation step by step:

  1. The case where k equals 1:

    • The implementation begins by setting ans to the original string s. This ans variable will keep track of the current smallest string.
    • Then, we perform a loop iteration for every character in the string except the last one (len(s) - 1 times).
      • In each iteration, the string s is modified by removing its first character and appending it at the end using s = s[1:] + s[0].
      • After modifying the string, we compare it with ans using the min() function, and if the modified string s is smaller, we update ans.
    • After testing all possible single-character rotations, we return the smallest string found, ans.

  2. The case where k is greater than 1:

    • This case is handled by one line of code: return "".join(sorted(s)).
      • The sorted() function is used to sort the characters of the string s into lexicographical order.
      • The "".join() function is then used to concatenate the sorted characters back into a string.
    • Since we can reorder the first k characters to eventually get any permutation of the string, we can always achieve a fully sorted string. So this method will return the lexicographically smallest possible string.

By using Python's built-in functions for sorting and string manipulation, the solution is both efficient and concise, leveraging the language's strengths in handling such operations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Example Walkthrough

Let's illustrate the solution approach with an example:

Suppose the input string is s = "bca" and k = 2.

Case where k > 1:

Since k is greater than 1, we are allowed to choose any of the first k letters and move it to the end of the string. This means we can eventually sort the entire string s. There are no limitations on how many times this operation can be performed, so the desired output is the lexicographically smallest sorted string. For the given string "bca", the sorted characters would be ["a", "b", "c"]. Joining these characters, we get the output "abc".

Let's detail the steps for this case:

  1. We call the sorted() function on the string s, which returns a list of the characters in s sorted in lexicographical order: ['a', 'b', 'c'].
  2. Then we concatenate these characters back into a string with the join() method: "".join(['a', 'b', 'c']) results in "abc".
  3. The final output "abc" is the lexicographically smallest string possible, so we return this string.

Now, let's consider the case when the input string s = "bca" and k = 1.

Case where k == 1:

Here, we can only move the first character to the end of the string. We have to try every possible rotation to find the lexicographically smallest string:

  1. The initial value of ans is the original string s, so ans = "bca".
  2. We perform a single-character rotation:
    1. Rotate once: remove the first character and append it to the end, s = "cab".
    2. Compare s with ans, s is lexicographically smaller, so ans = "cab".
  3. Repeat the rotation:
    1. Rotate again: s = "abc" (from the previous "cab").
    2. Compare s with ans, s is lexicographically smaller, so ans = "abc".
  4. No more rotations are needed because we've gone through the string once and ans now holds the smallest string after all rotations, ans = "abc".

In both scenarios, the output for the given example is "abc", but the approach to getting the result differs based on the value of k. If k is greater than 1, we sort the string; if k is 1, we perform rotations and keep track of the smallest result.

Solution Implementation

1class Solution:
2    def orderlyQueue(self, string: str, k: int) -> str:
3        # If k is equal to 1, we can only rotate the string.
4        if k == 1:
5            # Initialize the answer with the original string.
6            answer = string
7            # Iterate over the string, excluding the last character,
8            # since the last rotation would return the string to the original state.
9            for _ in range(len(string) - 1):
10                # Rotate the string by moving the first character to the end.
11                string = string[1:] + string[0]
12                # Update the answer if the new string is lexicographically smaller.
13                answer = min(answer, string)
14            # Return the lexicographically smallest string after all rotations.
15            return answer
16        # If k is greater than 1, we can sort the string to get the smallest possible string.
17        else:
18            # Convert the string into a sorted list of characters and join them back into a string.
19            return "".join(sorted(string))
20
1public class Solution {
2    public String orderlyQueue(String s, int k) {
3        // If k is greater than 1, we can achieve any permutation by rotation, 
4        // so we return the characters of the string sorted in alphabetical order.
5        if (k > 1) {
6            char[] chars = s.toCharArray();
7            Arrays.sort(chars);
8            return new String(chars);
9        }
10      
11        // If k is 1, we can only rotate the string. 
12        // We need to find the lexicographically smallest string possible by rotation.
13      
14        // Store the length of the string for convenience.
15        int stringLength = s.length();
16        // Initialize the minimum (lexicographically smallest) string as the original string.
17        String minimumString = s;
18
19        // Iterate through each possible rotation of the string.
20        for (int i = 1; i < stringLength; i++) {
21            // Create a rotated string by taking the substring from the current index to the end,
22            // and concatenating it with the substring from the start to the current index.
23            String rotatedString = s.substring(i) + s.substring(0, i);
24            // If the rotated string is lexicographically smaller than our current minimum,
25            // we update the minimum string.
26            if (rotatedString.compareTo(minimumString) < 0) {
27                minimumString = rotatedString;
28            }
29        }
30
31        // Return the lexicographically smallest string after checking all possible rotations.
32        return minimumString;
33    }
34}
35```
36
37Please make sure to include the necessary imports at the beginning of your Java file:
38
39```java
40import java.util.Arrays;
41
1class Solution {
2public:
3    // Function to return the lexicographically smallest string formed by rotating the string 's' if k=1,
4    // or returning the lexicographically smallest permutation of 's' if k>1.
5    string orderlyQueue(string s, int k) {
6        // If only one rotation is allowed at a time (k==1).
7        if (k == 1) {
8            // 'smallestString' will keep track of the lexicographically smallest string encountered.
9            string smallestString = s;
10            // Rotate the string and check each permutation.
11            for (int i = 0; i < s.size() - 1; ++i) {
12                // Rotate string left by one character.
13                s = s.substr(1) + s[0];
14                // Update 'smallestString' if the new rotation results in a smaller string.
15                if (s < smallestString) {
16                    smallestString = s;
17                }
18            }
19            // Return the lexicographically smallest string after rotating 's' by each possible number of positions.
20            return smallestString;
21        } else {
22            // If more than one rotation is allowed (k>1), return the smallest permutation.
23            // Sorting the string gives us the lexicographically smallest permutation.
24            sort(s.begin(), s.end());
25            return s;
26        }
27    }
28};
29
1function orderlyQueue(s: string, k: number): string {
2    // If k is greater than 1, sort the characters of the string alphabetically and return it,
3    // as we can achieve any permutation of the string by rotating it k times.
4    if (k > 1) {
5        return [...s].sort().join('');
6    }
7
8    // If k is 1, we can only rotate the string. Hence, we must find the lexicographically
9    // smallest string by rotating.
10  
11    // Store the length of the string for convenience.
12    const stringLength = s.length;
13    // Initialize the minimum (lexicographically smallest) string as the original string.
14    let minimumString = s;
15
16    // Iterate through each possible rotation of the string.
17    for (let i = 1; i < stringLength; i++) {
18        // Create a rotated string by taking the substring from current position to the end,
19        // and concatenating it with the substring from start to the current position.
20        const rotatedString = s.slice(i) + s.slice(0, i);
21        // If the rotated string is lexicographically smaller than our current minimum,
22        // update the minimum string.
23        if (rotatedString < minimumString) {
24            minimumString = rotatedString;
25        }
26    }
27
28    // Return the lexicographically smallest string after checking all rotations.
29    return minimumString;
30}
31
Not Sure What to Study? Take the 2-min Quiz：

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Time and Space Complexity

Time Complexity

The given code block has two conditions based on the value of k:

  • When k equals 1, the time complexity is O(n^2). This is because there is a loop that runs n-1 times (where n is the length of string s), and in each iteration, a string concatenation operation that takes O(n) time is performed. Since string concatenation is done inside the loop, the overall time complexity for this case is O(n) * O(n) = O(n^2).

  • When k is greater than 1, the time complexity is determined by the sorting operation, which is O(n log n) for typical sorting algorithms, where n is the length of the string s.

Space Complexity

  • When k equals 1, the space complexity is O(n) because a new string ans of maximum length n is created to store the interim and final results.

  • When k is greater than 1, the space complexity is also O(n) since a sorted copy of the string s is being created and returned.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

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.

←
↑TA 👨‍🏫