{"id":7035,"date":"2020-07-05T14:56:25","date_gmt":"2020-07-05T21:56:25","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7035"},"modified":"2020-07-08T13:34:28","modified_gmt":"2020-07-08T20:34:28","slug":"leetcode-1505-minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1505-minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits - \u5237\u9898\u627e\u5de5\u4f5c EP341\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/0EgQs2WWres?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given a string&nbsp;<code>num<\/code>&nbsp;representing&nbsp;<strong>the digits<\/strong>&nbsp;of&nbsp;a very large integer and an integer&nbsp;<code>k<\/code>.<\/p>\n\n\n\n<p>You are allowed to swap any two adjacent digits of the integer&nbsp;<strong>at most<\/strong>&nbsp;<code>k<\/code>&nbsp;times.<\/p>\n\n\n\n<p>Return&nbsp;<em>the minimum integer<\/em>&nbsp;you can obtain also as a string.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/06\/17\/q4_1.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> num = \"4321\", k = 4\n<strong>Output:<\/strong> \"1342\"\n<strong>Explanation:<\/strong> The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> num = \"100\", k = 1\n<strong>Output:<\/strong> \"010\"\n<strong>Explanation:<\/strong> It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> num = \"36789\", k = 1000\n<strong>Output:<\/strong> \"36789\"\n<strong>Explanation:<\/strong> We can keep the number without any swaps.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> num = \"22\", k = 22\n<strong>Output:<\/strong> \"22\"\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> num = \"9438957234785635408\", k = 23\n<strong>Output:<\/strong> \"0345989723478563548\"\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= num.length &lt;= 30000<\/code><\/li><li><code>num<\/code>&nbsp;contains&nbsp;<strong>digits<\/strong>&nbsp;only and doesn&#8217;t have&nbsp;<strong>leading zeros<\/strong>.<\/li><li><code>1 &lt;= k &lt;= 10^9<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy + Recursion<\/strong> <strong>(Update: TLE after 7\/6\/2020)<\/strong><\/h2>\n\n\n\n<p>Move the smallest number to the left and recursion on the right substring with length equals to n -= 1.<\/p>\n\n\n\n<p>4321 k = 4 =&gt; 1 + solve(432, 4-3) = 1 + solve(432, 1) = 1 + 3 + solve(42, 0) = 1 + 3 + 42 = 1342.<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string minInteger(string num, int k) {\n    const int n = num.size();\n    if (k >= n * (n - 1) \/ 2) {\n      sort(begin(num), end(num));\n      return num;\n    }\n    \n    int s = 0;\n    while (k > 0 && s < n) {\n      auto bit = begin(num);\n      auto it = min_element(bit + s, bit + min(s + k + 1, n));\n      k -= distance(bit + s, it);\n      rotate(bit + (s++), it, next(it));\n    }\n    return num;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Binary Indexed Tree \/ Fenwick Tree<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1505-ep341-1.png\" alt=\"\" class=\"wp-image-7043\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1505-ep341-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1505-ep341-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1505-ep341-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1505-ep341-2.png\" alt=\"\" class=\"wp-image-7044\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1505-ep341-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1505-ep341-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1505-ep341-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1505-ep341-3.png\" alt=\"\" class=\"wp-image-7045\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1505-ep341-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1505-ep341-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1505-ep341-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Moving elements in a string is a very expensive operation, basically O(n) per op. Actually, we don't need to move the elements physically, instead we track how many elements before i has been moved to the \"front\". Thus we know the cost to move the i-th element to the \"front\", which is i - elements_moved_before_i or prefix_sum(0~i-1) if we mark moved element as 1.<\/p>\n\n\n\n<p>We know BIT \/ Fenwick Tree is good for dynamic prefix sum computation which helps to reduce the time complexity to O(nlogn).<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Fenwick {\n public:\n  explicit Fenwick(int n) : sums_(n + 1) {}\n  \n  void update(int i, int delta) {\n    ++i;\n    while (i <  sums_.size()) {\n      sums_[i] += delta;\n      i += i &#038; -i;\n    }\n  }\n  \n  int query(int i) {\n    ++i;\n    int ans = 0;\n    while (i > 0) {\n      ans += sums_[i];\n      i -= i & -i;\n    }\n    return ans;\n  }\n private:\n  vector<int> sums_;\n};\n\nclass Solution {\npublic:\n  string minInteger(string num, int k) {    \n    const int n = num.length();\n    vector<queue<int>> pos(10);\n    for (int i = 0; i < n; ++i)\n      pos[num[i] - '0'].push(i);    \n    \n    Fenwick tree(n);\n    vector<int> used(n);\n    string ans;\n    while (k > 0 & ans.length() < n) {      \n      for (int d = 0; d < 10; ++d) {\n        if (pos[d].empty()) continue;\n        const int i = pos[d].front();\n        const int cost = i - tree.query(i - 1);\n        if (cost > k) continue;        \n        k -= cost;\n        ans += ('0' + d);\n        tree.update(i, 1);\n        used[i] = true;\n        pos[d].pop();\n        break;\n      }\n    };\n    \n    for (int i = 0; i < n; ++i)\n      if (!used[i]) ans += num[i];\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\n\/\/ Author: Huahua\nclass Solution {\n  class Fenwick {\n    private int[] sums;\n    \n    public Fenwick(int n) {\n      this.sums = new int[n + 1];\n    }\n    \n    public void update(int i, int delta) {\n      ++i;\n      while (i < sums.length) {\n        this.sums[i] += delta;\n        i += i &#038; -i;\n      }\n    }\n    \n    public int query(int i) {\n      int ans = 0;\n      ++i;\n      while (i > 0) {\n        ans += this.sums[i];\n        i -= i & -i;\n      }\n      return ans;\n    }\n  }\n  \n  public String minInteger(String num, int k) {\n    int n = num.length();\n    var used = new boolean[n];\n    var pos = new ArrayList<ArrayDeque<Integer>>();\n    for (int i = 0; i <= 9; ++i)\n      pos.add(new ArrayDeque<Integer>());    \n    for (int i = 0; i < num.length(); ++i)\n      pos.get(num.charAt(i) - '0').offer(i);\n    var tree = new Fenwick(n);\n    var sb = new StringBuilder();\n    while (k > 0 && sb.length() < n) {\n      for (int d = 0; d <= 9; ++d) {\n        Integer i = pos.get(d).peek();\n        if (i == null) continue;\n        int cost = i - tree.query(i - 1);\n        if (cost > k) continue;        \n        sb.append((char)(d + '0'));\n        k -= cost;\n        pos.get(d).removeFirst();\n        tree.update(i, 1);\n        used[i] = true;\n        break;\n      }\n    }\n    for (int i = 0; i < n; ++i)\n      if (!used[i]) sb.append(num.charAt(i));\n    return sb.toString();\n  }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\n# Author: Huahua\nclass Fenwick:\n  def __init__(self, n):\n    self.sums = [0] * (n + 1)\n  \n  def query(self, i):\n    ans = 0\n    i += 1\n    while i > 0:\n      ans += self.sums[i];\n      i -= i & -i\n    return ans\n  \n  def update(self, i, delta):\n    i += 1\n    while i < len(self.sums):\n      self.sums[i] += delta\n      i += i &#038; -i\n\n\nclass Solution:\n  def minInteger(self, num: str, k: int) -> str:    \n    n = len(num)\n    used = [False] * n\n    pos = [deque() for _ in range(10)]\n    for i, c in enumerate(num):\n      pos[ord(c) - ord(\"0\")].append(i)\n    tree = Fenwick(n)\n    ans = []\n    while k > 0 and len(ans) < n:\n      for d in range(10):\n        if not pos[d]: continue\n        i = pos[d][0]\n        cost = i - tree.query(i - 1)\n        if cost > k: continue\n        k -= cost\n        ans.append(chr(d + ord(\"0\")))\n        tree.update(i, 1)\n        used[i] = True\n        pos[d].popleft()\n        break\n    for i in range(n):\n      if not used[i]: ans.append(num[i])\n    return \"\".join(ans)\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a string&nbsp;num&nbsp;representing&nbsp;the digits&nbsp;of&nbsp;a very large integer and an integer&nbsp;k. You are allowed to swap any two adjacent digits of the integer&nbsp;at most&nbsp;k&nbsp;times. Return&nbsp;the minimum&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[629,88,628,630,179],"class_list":["post-7035","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-bubble-sort","tag-greedy","tag-min-number","tag-reverse-paris","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7035","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=7035"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7035\/revisions"}],"predecessor-version":[{"id":7049,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7035\/revisions\/7049"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7035"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7035"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7035"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}