Orderly Queue

hard string sorting rotation

Problem

You are given a string s and an integer k. You may repeatedly choose one of the first k characters of s, remove it, and append it to the end of the string. Return the lexicographically smallest string obtainable after any number of such moves.

Inputs = "cba", k = 1

Output"acb"

With k = 1 only the first character can move, so we are limited to rotations of s. The rotations are "cba", "bac", "acb" — the smallest is "acb".

s (letters)

def orderly_queue(s, k):
    if k > 1:
        return "".join(sorted(s))
    best = s
    for i in range(1, len(s)):
        rot = s[i:] + s[:i]
        if rot < best:
            best = rot
    return best

function orderlyQueue(s, k) {
  if (k > 1) return s.split("").sort().join("");
  let best = s;
  for (let i = 1; i < s.length; i++) {
    const rot = s.slice(i) + s.slice(0, i);
    if (rot < best) best = rot;
  }
  return best;
}

class Solution {
    public String orderlyQueue(String s, int k) {
        if (k > 1) {
            char[] a = s.toCharArray();
            Arrays.sort(a);
            return new String(a);
        }
        String best = s;
        for (int i = 1; i < s.length(); i++) {
            String rot = s.substring(i) + s.substring(0, i);
            if (rot.compareTo(best) < 0) best = rot;
        }
        return best;
    }
}

string orderlyQueue(string s, int k) {
    if (k > 1) {
        sort(s.begin(), s.end());
        return s;
    }
    string best = s;
    for (int i = 1; i < (int)s.size(); i++) {
        string rot = s.substr(i) + s.substr(0, i);
        if (rot < best) best = rot;
    }
    return best;
}

Explanation

The whole trick is realizing the answer depends entirely on whether k is 1 or bigger. These two cases behave completely differently, so the solution splits into a clean case analysis.

When k > 1, you can pick from the first two (or more) characters, and it turns out that lets you perform adjacent swaps. With enough swaps you can reach any rearrangement of the letters. So the smallest possible string is simply the characters sorted in ascending order: "".join(sorted(s)).

When k == 1, only the very first character can move to the end. Repeating that just produces the rotations of s and nothing else. So we generate each rotation s[i:] + s[:i] and keep the lexicographically smallest one in best.

Example: s = "cba", k = 1. The rotations are "cba", "bac", and "acb". Comparing them, "acb" is the smallest, so that is the answer. (If k were 2 instead, sorting would give "abc".)

Time: O(n²) when k = 1, O(n log n) when k > 1 Space: O(n)