Orderly Queue

• The core idea is to analyze the problem based on the value of k.
• Case 1: k > 1
  • When k is greater than 1, we have enough flexibility to swap any two adjacent characters in the string. This is because we can bring any two adjacent characters to the first two positions (by repeatedly moving the first character to the end), and since k > 1, we can manipulate them. For instance, to swap s_1 and s_2, we can move s_1 to the end, then cycle all other characters through until s_2 is at the front followed by s_1.
  • The ability to swap any adjacent pair implies we can achieve any permutation of the string (this is the principle behind bubble sort).
  • Therefore, the lexicographically smallest string we can form is simply the sorted version of the original string s.
• Case 2: k = 1
  • When k is 1, the only allowed move is to take the first character and move it to the end. This is a cyclic shift or rotation of the string.
  • The problem reduces to finding the lexicographically smallest string among all possible rotations of s.
  • This approach implements a straightforward, albeit inefficient, method for this case: generate all n rotations and compare them to find the smallest one.

The algorithm is split into two main scenarios:

1. If k > 1: We can achieve any permutation of the string s. The proof sketch is that with k>1, we can perform an adjacent swap. Since any permutation can be reached by a series of adjacent swaps (like in bubble sort), we can form any arrangement of characters. To get the lexicographically smallest string, we just need to sort the characters of s. This can be done by converting the string to a character array, sorting it, and converting it back to a string.

2. If k = 1: We can only perform cyclic shifts. To find the lexicographically smallest one, this approach iterates through all n possible rotations. It maintains a variable smallest that stores the best rotation found so far. In a loop, it generates the next rotation and updates smallest if the new rotation is lexicographically smaller.

1import java.util.Arrays;2 3class Solution {4    public String orderlyQueue(String s, int k) {5        if (k > 1) {6            char[] chars = s.toCharArray();7            Arrays.sort(chars);8            return new String(chars);9        } else { // k == 110            String smallest = s;11            StringBuilder sb = new StringBuilder(s);12            // Iterate through all n-1 possible rotations13            for (int i = 1; i < s.length(); i++) {14                // Rotate the string by one position15                char first = sb.charAt(0);16                sb.deleteCharAt(0);17                sb.append(first);18                String rotated = sb.toString();19                // Compare with the smallest found so far20                if (rotated.compareTo(smallest) < 0) {21                    smallest = rotated;22                }23            }24            return smallest;25        }26    }27}

• The logic for the k > 1 case is identical to the previous approach: sort the string. This is the optimal strategy for this case and takes O(n log n) time.
• For the k = 1 case, instead of an O(n^2) search, this approach uses an efficient O(n) algorithm to find the lexicographically smallest rotation.
• One such linear-time algorithm works by maintaining two pointers, i and j, representing the starting indices of two candidate rotations.
• We compare the rotations starting at i and j character by character. Let k be the number of characters they have in common from the start.
• If s[i+k] > s[j+k], the rotation at i is worse, so we can discard it and advance i past the compared block (i = i + k + 1).
• If s[i+k] < s[j+k], the rotation at j is worse, so we advance j (j = j + k + 1).
• This process continues until one pointer has traversed the entire string length, and the minimum of the final i and j gives the starting index of the smallest rotation.

This solution also splits the problem based on k.

• If k > 1: The logic is unchanged. Sorting the string is the optimal solution, taking O(n log n) time.

• If k = 1: We use a linear-time, two-pointer algorithm to find the lexicographically smallest rotation. This avoids the quadratic complexity of naive comparison. The implementation can be made cleaner by working on a duplicated string s+s, which simplifies index handling.

By optimizing the k=1 case to O(n), the overall time complexity becomes max(O(n log n), O(n)), which is O(n log n). This is asymptotically the best possible solution.

1import java.util.Arrays;2 3class Solution {4    public String orderlyQueue(String s, int k) {5        if (k > 1) {6            char[] chars = s.toCharArray();7            Arrays.sort(chars);8            return new String(chars);9        } else { // k == 1, solved in O(n)10            return findSmallestRotation(s);11        }12    }13 14    // Finds the lexicographically smallest rotation of a string in O(n) time.15    private String findSmallestRotation(String s) {16        int n = s.length();17        String s2 = s + s; // Use a doubled string to simplify comparisons18        int i = 0; // Index of the first candidate rotation19        int j = 1; // Index of the second candidate rotation20        21        while (i < n && j < n) {22            int k = 0; // Number of matching characters23            while (k < n && s2.charAt(i + k) == s2.charAt(j + k)) {24                k++;25            }26            if (k == n) { // The entire string matches, all rotations are the same27                break;28            }29            // If character at s[i+k] is greater, rotation i is not the smallest.30            // The new candidate for i can start after the mismatched block.31            if (s2.charAt(i + k) > s2.charAt(j + k)) {32                i = i + k + 1;33            } else { // s2.charAt(i + k) < s2.charAt(j + k)34                j = j + k + 1;35            }36            // Ensure i and j are not the same37            if (i == j) {38                j++;39            }40        }41        // The starting index of the smallest rotation is the minimum of the final candidates.42        int minIndex = Math.min(i, j);43        return s2.substring(minIndex, minIndex + n);44    }45}