Algorithm

1. Let $n$ denote the length of the string. We should attach this problem via the lens of permutation groups.
2. If $k=1,$ then the admissable cycles is $(1n)$, which is not a generating set of $S(n).$ Hence, there is no other way to than brute force search to find out the lexicographically smallest permutation.
3. If $k>1,$ then the list of cycles, which we denote as $C(n),$ is a generating set of $S(n).$ To prove this, it suffices to prove that $C(n)$ contains all tranpositions $(i,i+1).$ To do so, we first move $S[0:i-1]$ to the end and then move $S[i+1]$ to the end, and then $S[i],$ and then acting $(1n)$ on $S$ until everthing else are back into their original positions. There is a precise mathematical formulation for this, but we won’t bother writing it out.
4. So the algorithm is a simple case analysis: if $k=1$ do brute-force search, otherwise we sort $S$ and return sorted[S].

Code

class Solution {

 public:
  string orderlyQueue(string S, int K) {
#define ALL(x) begin(x), end(x)

    auto next = [&](string str) { return string(begin(str) + 1, end(str)) + (*begin(str)); };

    if (K == 1) {
      const auto all_permutations = [&](vector<string> self = {}) {
        self.emplace_back(S);
        for (int i = 0; i < size(S); ++i)
          self.emplace_back(next(self.back()));
        return self;
      }();
      return *min_element(ALL(all_permutations));
    }
    else {
      return [&](string solution = {}) {
        std::copy(ALL(S), std::back_inserter(solution));
        std::sort(ALL(solution));
        return solution;
      }();
    }

  }
};