LeetCode Problem 899

Difficulty: 🔴 Hard
Topics: Math, String, Sorting

Solution

LeetCode 899 - Orderly Queue

Problem Understanding

This problem gives us a string s and an integer k. We are allowed to repeatedly perform one operation:

• Choose one of the first k characters of the string.
• Remove that character from its current position.
• Append it to the end of the string.

Our goal is to determine the lexicographically smallest string that can be produced after performing this operation any number of times.

A lexicographically smaller string is one that would appear earlier in dictionary order. For example:

• "abc" is smaller than "acb"
• "aaabc" is smaller than "aacab"

The input consists of:

• A lowercase English string s
• An integer k

The constraints are:

• 1 <= k <= s.length <= 1000
• The string contains only lowercase English letters

The small input size suggests that even O(n^2) solutions are acceptable, but exponential exploration of all possible states would still be far too slow.

The key difficulty is understanding how the allowed operation changes depending on the value of k.

When k = 1, we may only move the first character to the end. This means every operation is simply a rotation of the string.

When k > 1, the behavior changes dramatically. Having access to more than one of the leading characters gives enough freedom to rearrange the string into any permutation. That means the lexicographically smallest possible result is simply the sorted string.

Several edge cases are important:

• A single-character string should return itself.
• Strings with repeated characters require careful lexicographic comparison.
• When k = 1, we must only consider rotations, not arbitrary rearrangements.
• When the string is already minimal, the algorithm should correctly return it unchanged.

Approaches

Brute Force Approach

A brute-force solution would treat the problem as a graph search over all reachable strings.

Starting from the initial string, we could generate every possible next state by selecting each of the first k characters and moving it to the end. Using BFS or DFS, we could explore all reachable configurations while keeping track of the smallest lexicographic string encountered.

This approach is correct because it explicitly enumerates every reachable state.

However, it is computationally infeasible. A string of length n can have up to n! permutations. Even though not all permutations may be reachable for every k, the state space grows explosively. With n <= 1000, exhaustive exploration is impossible.

Key Insight

The crucial observation is that the problem behaves completely differently depending on whether k equals 1 or is greater than 1.

When k = 1, the only allowed move is taking the first character and appending it to the end. Repeating this operation generates all cyclic rotations of the string and nothing else.

For example:

"cba"
-> "bac"
-> "acb"
-> "cba"

So for k = 1, the answer is simply the smallest rotation of the string.

When k > 1, we gain much more flexibility. In fact, we can simulate adjacent swaps and ultimately generate any permutation of the string. Since any permutation becomes reachable, the lexicographically smallest possible arrangement is the fully sorted string.

This transforms the problem into:

• k = 1: find the minimum rotation
• k > 1: return sorted characters

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all reachable string states
Optimal	O(n²) for k=1, O(n log n) for k>1	O(n)	Uses rotation property or sorting insight

Algorithm Walkthrough

Case 1: k == 1

When k equals 1, every operation moves the first character to the end. This means we can only produce rotations of the original string.

To find the lexicographically smallest result:

1. Initialize the answer as the original string.
2. Generate every possible rotation.
3. Compare each rotation with the current best answer.
4. Update the answer whenever a smaller rotation is found.
5. Return the smallest rotation.

For a string of length n, there are exactly n distinct rotations.

Case 2: k > 1

When k is greater than 1, we can rearrange characters freely.

The important observation is that with access to at least two leading characters, we can effectively perform adjacent swaps through repeated operations. Since adjacent swaps can generate any permutation, every ordering of the characters becomes achievable.

To obtain the lexicographically smallest possible string:

1. Convert the string into a list of characters.
2. Sort the characters in ascending order.
3. Join them back into a string.
4. Return the result.

Why it works

For k = 1, the operation preserves the cyclic order of characters, so only rotations are reachable. Therefore, the smallest reachable string must be the minimum rotation.

For k > 1, the operation set is powerful enough to simulate arbitrary permutations. Since the lexicographically smallest permutation of a string is its sorted order, sorting produces the optimal answer.

Python Solution

class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k == 1:
            smallest = s
            n = len(s)

            for i in range(1, n):
                rotation = s[i:] + s[:i]
                if rotation < smallest:
                    smallest = rotation

            return smallest

        return "".join(sorted(s))

The implementation begins by checking whether k equals 1.

In this special case, the code enumerates every rotation of the string. A rotation is formed by splitting the string at index i and swapping the two halves:

s[i:] + s[:i]

Each generated rotation is compared lexicographically against the current best answer.

If k is greater than 1, the implementation immediately returns the sorted version of the string because all permutations are reachable.

The use of Python's built-in sorted() function keeps the implementation concise and efficient.

Go Solution

package main

import (
	"sort"
)

func orderlyQueue(s string, k int) string {
	if k == 1 {
		smallest := s
		n := len(s)

		for i := 1; i < n; i++ {
			rotation := s[i:] + s[:i]

			if rotation < smallest {
				smallest = rotation
			}
		}

		return smallest
	}

	chars := []byte(s)
	sort.Slice(chars, func(i, j int) bool {
		return chars[i] < chars[j]
	})

	return string(chars)
}

The Go implementation follows the same logic as the Python solution.

For k == 1, it generates every rotation using string slicing and tracks the lexicographically smallest result.

For k > 1, the string is converted into a byte slice so it can be sorted in place using sort.Slice.

Since the input only contains lowercase English letters, byte-based sorting is completely safe and efficient.

Worked Examples

Example 1

Input: s = "cba", k = 1

Since k = 1, we only examine rotations.

Rotation Index	Rotation	Current Smallest
0	"cba"	"cba"
1	"bac"	"bac"
2	"acb"	"acb"

Final answer:

"acb"

Example 2

Input: s = "baaca", k = 3

Since k > 1, we can rearrange the characters arbitrarily.

Sort the characters:

Original Characters	Sorted Characters
b a a c a	a a a b c

Join them together:

"aaabc"

Final answer:

"aaabc"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²) for k=1, O(n log n) for k>1	Rotation generation requires O(n) work for each of n rotations
Space	O(n)	Rotations and sorted strings require additional storage

When k = 1, we generate n rotations, and each rotation construction takes O(n) time, resulting in O(n²) total complexity.

When k > 1, sorting dominates the runtime, giving O(n log n) complexity.

The auxiliary space complexity is O(n) because new strings or character arrays are created during processing.

Test Cases

solution = Solution()

assert solution.orderlyQueue("cba", 1) == "acb"        # basic rotation case
assert solution.orderlyQueue("baaca", 3) == "aaabc"    # arbitrary permutation case
assert solution.orderlyQueue("a", 1) == "a"            # single character
assert solution.orderlyQueue("abc", 1) == "abc"        # already minimal rotation
assert solution.orderlyQueue("bca", 1) == "abc"        # rotation becomes smallest
assert solution.orderlyQueue("daily", 2) == "adily"    # sorting with k > 1
assert solution.orderlyQueue("zzz", 1) == "zzz"        # repeated characters
assert solution.orderlyQueue("leetcode", 1) == "codeleet"  # nontrivial rotation
assert solution.orderlyQueue("leetcode", 5) == "cdeeelot"  # sorted permutation
assert solution.orderlyQueue("aaaa", 2) == "aaaa"      # all identical characters

Test	Why
"cba", 1	Validates rotation-only behavior
"baaca", 3	Validates arbitrary permutation behavior
"a", 1	Tests minimum input size
"abc", 1	Tests already minimal rotation
"bca", 1	Ensures rotations are checked correctly
"daily", 2	Verifies sorting path
"zzz", 1	Tests repeated identical characters
"leetcode", 1	Tests larger rotation search
"leetcode", 5	Tests larger sorting case
"aaaa", 2	Tests all-equal characters

Edge Cases

One important edge case is a single-character string. Since there is only one possible arrangement, both the rotation logic and sorting logic should return the original string unchanged. The implementation handles this naturally because the rotation loop performs zero iterations and sorting a one-character string changes nothing.

Another important case is repeated characters. Lexicographic comparisons can become tricky when many prefixes are identical. For example, "baaca" contains multiple 'a' characters. The implementation correctly relies on standard string comparison operations, which compare characters sequentially until a difference is found.

A third important edge case occurs when k = 1. A common mistake is assuming that any permutation becomes reachable. This is incorrect because the operation only produces cyclic rotations. The implementation explicitly separates this case and examines only valid rotations.

A fourth subtle case is when the original string is already the smallest possible result. For example, "abc" with k = 1 already represents the minimum rotation. The implementation initializes the answer with the original string, ensuring it remains unchanged if no smaller rotation exists.