Vultr DocsLatest Content

Orderly Queue

Updated on 08 July, 2025
Orderly Queue header image

Problem Statement

Given a string s and an integer k, the task is to construct the lexicographically smallest string possible by selecting any of the first k characters from s and appending it to the end of the string. This operation can be applied repeatedly an unlimited number of times. The challenge involves not just moving characters but strategically doing so to achieve the smallest possible dictionary order of the string.

Examples

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 and Intuition

  1. Understanding Lexicographical Order: Before diving into potential solutions, it's essential to grasp what "lexicographically smallest" means. It is akin to alphabetical order, but extends beyond to any characters with a defined sorting order.

  2. Applying Constraints Creatively: Given that you can only move one of the first k characters to the end of the string, the value of k plays a crucial role. If k is 1, your options are quite limited as you can only move the first character. If k equals the length of s, you have the flexibility to rearrange any character from the entire string.

  3. Iterative Exploration:

    • For a smaller k, one would consider moving the smallest of the first k characters to the rear of the string repeatedly until no further lexical reduction is possible.
    • If any character within the first k characters is smaller than the leading character, moving the smallest possible character could directly influence the resulting string's order positively.

  4. Optimization by Observation: From the examples, observe how strategic movement of characters quickly leads to the desired output. In cases where direct sorting isn't feasible due to constraints, simulating the operations or creatively determining the next best move becomes crucial.

By following this approach, the goal is to use the operations allowed to rearrange the string into its lowest possible order given the constraint of only being able to move the first k characters to the end. Each operation should be chosen to progressively bring the string closer to the desired lexicographical order.

Solutions

  • Java
java 
class Solver {
    public String arrangeString(String str, int k) {
        if (k == 1) {
            String result = str;
            for (int i = 0; i < str.length(); i++) {
                String rotated = str.substring(i) + str.substring(0, i);
                if (rotated.compareTo(result) < 0) {
                    result = rotated;
                }
            }
            return result;
        } else {
            char[] characterArray = str.toCharArray();
            Arrays.sort(characterArray);
            return new String(characterArray);
        }
    }
}

The problem "Orderly Queue" involves arranging a string in an orderly fashion depending on a given condition represented by the integer k. The solution is implemented in Java within a class named Solver. It offers a method arrangeString that manipulates the input string str based on the value of k.

  • If k equals 1:

    • The function seeks the lexicographically smallest string possible by rotating the string. This is done by trying all possible rotations and keeping track of the smallest result found after each rotation.
    • The method utilizes two nested loops where the outer loop iterates through the starting indices of the string and the inner loop performs the comparison of the rotated string with the current smallest result string.

  • If k is greater than 1:

    • The solution is straightforward: sort the characters of the string in alphabetical order. This is achieved using the Java Arrays.sort() method on the character array derived from the string.

The method returns the smallest lexicographically ordered string for k equal to 1, and a directly sorted string when k is greater than 1. As a result, depending on the value of k, the method appropriately handles string manipulation to return the expected output.

  • Python
python 
class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k == 1:
            return min(s[i:] + s[:i] for i in range(len(s)))
        else:
            return ''.join(sorted(s))

The solution addresses the "Orderly Queue" problem by designing a method rearrangeString that takes two parameters: a string s and an integer k. The method functions based on the value of k:

  • When k is 1, the method explores all possible rotations of the string s and selects the lexicographically smallest rotation. Perform this by concatenating the substring from the current index to the end and the substring from the start to the current index. Iterate this process through each character index of string s.

  • For values of k greater than 1, the method simply returns the characters of string s sorted in lexicographical (alphabetical) order.

This Python implementation uses convenient list comprehensions and string manipulation techniques to accomplish the rearrangement efficiently.

The method returns the reordered string based on the aforementioned conditions, optimizing the order of s as per the provided value of k.

Comments

No comments yet.