{"id":6397,"date":"2020-03-07T23:16:42","date_gmt":"2020-03-08T07:16:42","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6397"},"modified":"2020-03-07T23:23:04","modified_gmt":"2020-03-08T07:23:04","slug":"leetcode-1370-increasing-decreasing-string","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1370-increasing-decreasing-string\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1370. Increasing Decreasing String"},"content":{"rendered":"\n

Given a string s<\/code>. You should re-order the string using the following algorithm:<\/p>\n\n\n\n

  1. Pick the smallest<\/strong> character from s<\/code> and append<\/strong> it to the result.<\/li>
  2. Pick the smallest<\/strong> character from s<\/code> which is greater than the last appended character to the result and append<\/strong> it.<\/li>
  3. Repeat step 2 until you cannot pick more characters.<\/li>
  4. Pick the largest<\/strong> character from s<\/code> and append<\/strong> it to the result.<\/li>
  5. Pick the largest<\/strong> character from s<\/code> which is smaller than the last appended character to the result and append<\/strong> it.<\/li>
  6. Repeat step 5 until you cannot pick more characters.<\/li>
  7. Repeat the steps from 1 to 6 until you pick all characters from s<\/code>.<\/li><\/ol>\n\n\n\n

    In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.<\/p>\n\n\n\n

    Return the result string<\/em> after sorting s<\/code> with this algorithm.<\/p>\n\n\n\n

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

    Input:<\/strong> s = \"aaaabbbbcccc\"\nOutput:<\/strong> \"abccbaabccba\"\nExplanation:<\/strong> After steps 1, 2 and 3 of the first iteration, result = \"abc\"\nAfter steps 4, 5 and 6 of the first iteration, result = \"abccba\"\nFirst iteration is done. Now s = \"aabbcc\" and we go back to step 1\nAfter steps 1, 2 and 3 of the second iteration, result = \"abccbaabc\"\nAfter steps 4, 5 and 6 of the second iteration, result = \"abccbaabccba\"\n<\/pre>\n\n\n\n
    Example 2:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> s = \"rat\"\nOutput:<\/strong> \"art\"\nExplanation:<\/strong> The word \"rat\" becomes \"art\" after re-ordering it with the mentioned algorithm.\n<\/pre>\n\n\n\n
    Example 3:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> s = \"leetcode\"\nOutput:<\/strong> \"cdelotee\"\n<\/pre>\n\n\n\n
    Example 4:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> s = \"ggggggg\"\nOutput:<\/strong> \"ggggggg\"\n<\/pre>\n\n\n\n
    Example 5:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> s = \"spo\"\nOutput:<\/strong> \"ops\"\n<\/pre>\n\n\n\n
    Constraints:<\/strong><\/p>\n\n\n\n
    • 1 <= s.length <= 500<\/code><\/li>
    • s<\/code> contains only lower-case English letters.<\/li><\/ul>\n\n\n\n
      Solution: Counting frequency of each character<\/strong><\/h2>\n\n\n\n
      Time complexity: O(n * 26)
      Space complexity: O(26) <\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string sortString(string s) {\n    vector count(26);\n    for (char c : s) ++count[c - 'a'];\n    string ans;\n    while (ans.length() != s.length()) {\n      for (char c = 'a'; c <= 'z'; ++c)\n        if (--count[c - 'a'] >= 0)\n          ans += c;\n      for (char c = 'z'; c >= 'a'; --c)\n        if (--count[c - 'a'] >= 0)\n          ans += c;      \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
      \n
      Python3<\/h2>\n
      \n\n
      \n# Author: Huahua\nclass Solution:\n  def sortString(self, s: str) -> str:\n    seq = string.ascii_lowercase + string.ascii_lowercase[::-1]\n    count = collections.Counter(s)\n    ans = \"\"\n    while len(ans) != len(s):\n      for c in seq:\n        if count[c] > 0:\n          ans += c\n          count[c] -= 1\n    return ans\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      Given a string s. You should re-order the string using the following algorithm: Pick the smallest character from s and append it to the result. Pick the smallest character from s which is greater than the…<\/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":[8,222,24,4],"class_list":["post-6397","post","type-post","status-publish","format-standard","hentry","category-string","tag-counting","tag-easy","tag-frequency","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6397","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=6397"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6397\/revisions"}],"predecessor-version":[{"id":6399,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6397\/revisions\/6399"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6397"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6397"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6397"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}