Orderly Queue — LeetCode 899 Python Solution

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

Example

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

Python solution

class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k == 1:
            ans = s
            for _ in range(len(s) - 1):
                s = s[1:] + s[0]
                ans = min(ans, s)
            return ans
        return "".join(sorted(s))

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 899. Orderly Queue is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems