{"id":3806,"date":"2018-09-01T23:07:48","date_gmt":"2018-09-02T06:07:48","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3806"},"modified":"2018-09-01T23:09:34","modified_gmt":"2018-09-02T06:09:34","slug":"leetcode-899-orderly-queue","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-899-orderly-queue\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 899. Orderly Queue"},"content":{"rendered":"
\n

Problem<\/strong><\/h1>\n

A string\u00a0S<\/code>\u00a0of lowercase letters is given.\u00a0 Then, we may make any number of\u00a0moves<\/em>.<\/p>\n

In each move, we\u00a0choose one\u00a0of the first\u00a0K<\/code>\u00a0letters (starting from the left), remove it,\u00a0and place it at the end of the string.<\/p>\n

Return the lexicographically smallest string we could have after any number of moves.<\/p>\n

\n

Example 1:<\/strong><\/p>\n

Input: <\/strong>S = \"cba\"<\/span>, K = 1<\/span>\r\nOutput: <\/strong>\"acb\"<\/span>\r\nExplanation: <\/strong>\r\nIn the first move, we move the 1st character (\"c\") to the end, obtaining the string \"bac\".\r\nIn the second move, we move the 1st character (\"b\") to the end, obtaining the final result \"acb\".\r\n<\/pre>\n
\n
Example 2:<\/strong><\/p>\n
Input: <\/strong>S = \"baaca\"<\/span>, K = 3<\/span>\r\nOutput: <\/strong>\"aaabc\"<\/span>\r\nExplanation: <\/strong>\r\nIn the first move, we move the 1st character (\"b\") to the end, obtaining the string \"aacab\".\r\nIn the second move, we move the 3rd character (\"c\") to the end, obtaining the final result \"aaabc\".\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. 1 <= K <= S.length\u00a0<= 1000<\/code><\/li>\n
  2. S<\/code>\u00a0consists of lowercase letters only.<\/li>\n<\/ol>\n
    Solution: Rotation or Sort?<\/strong><\/h1>\n
    if \\(k =1\\), we can only rotate the string.<\/p>\n
    if \\(k > 1\\), we can bubble sort the string.<\/p>\n
    Time complexity: O(n^2)<\/p>\n
    Space complexity: O(n)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 4 ms\r\nclass Solution {\r\npublic:\r\n  string orderlyQueue(string S, int K) {\r\n    if (K > 1) {\r\n      sort(begin(S), end(S));\r\n      return S;\r\n    }\r\n    \r\n    string ans = S;\r\n    for (int i = 1; i < S.size(); ++i)\r\n      ans = min(ans, S.substr(i) +  S.substr(0, i));\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div>
    Java<\/h2>\n
    \n\n
    \/\/ Author: Huahua\r\nclass Solution {\r\n  public String orderlyQueue(String S, int K) {\r\n    if (K > 1) {\r\n      char[] chars = S.toCharArray();\r\n      Arrays.sort(chars);\r\n      return new String(chars);\r\n    }\r\n    \r\n    String ans = S;\r\n    for (int i = 1; i < S.length(); ++i) {\r\n      String tmp = S.substring(i) + S.substring(0, i);\r\n      if (tmp.compareTo(ans) < 0) ans = tmp;        \r\n    }\r\n    return ans;\r\n  }\r\n}<\/pre>\n\n<\/div>
    Python3 SC O(n^2)<\/h2>\n
    \n\n
    # Author: Huahua 48 ms\r\nclass Solution:\r\n  def orderlyQueue(self, S, K):\r\n    if K > 1: return ''.join(sorted(S))\r\n    return min([S[i:] + S[0:i] for i in range(0, len(S))])<\/pre>\n\n<\/div>
    Python3 SC O(n)<\/h2>\n
    \n\n
    # Author: Huahua 36 ms\r\nclass Solution:\r\n  def orderlyQueue(self, S, K):\r\n    if K > 1: return ''.join(sorted(S))\r\n    ans = S\r\n    for i in range(0, len(S)):\r\n      ans = min(ans, S[i:] + S[0:i])\r\n    return ans<\/pre>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem A string\u00a0S\u00a0of lowercase letters is given.\u00a0 Then, we may make any number of\u00a0moves. In each move, we\u00a0choose one\u00a0of the first\u00a0K\u00a0letters (starting from the left),…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[217,367,23,4],"class_list":["post-3806","post","type-post","status-publish","format-standard","hentry","category-string","tag-hard","tag-rotation","tag-sort","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3806","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3806"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3806\/revisions"}],"predecessor-version":[{"id":3810,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3806\/revisions\/3810"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3806"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3806"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3806"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}