1
// Time O(n)
2
// Space O(n)
3
class Solution {
4
  public String orderlyQueue(String s, int k) {
5
    int n = s.length();
6
    String ans = "";
7
    if (k == 1) {
8
      s += s; // add itself again
9
      for (int i = 0; i < n; i++)
10
        if (ans.isEmpty() || s.substring(i, i + n).compareTo(ans) < 0) {
11
          ans = s.substring(i, i + n);
12
        }
13
    } else {
14
      char[] arr = s.toCharArray();
15
      Arrays.sort(arr);
16
      ans = String.valueOf(arr);
17
    }
18
    return ans;
19
  }
20
}