{"id":8436,"date":"2021-05-08T22:06:28","date_gmt":"2021-05-09T05:06:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8436"},"modified":"2021-05-08T22:06:47","modified_gmt":"2021-05-09T05:06:47","slug":"leetcode-1850-minimum-adjacent-swaps-to-reach-the-kth-smallest-number","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1850-minimum-adjacent-swaps-to-reach-the-kth-smallest-number\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number"},"content":{"rendered":"\n<p>You are given a string&nbsp;<code>num<\/code>, representing a large integer, and an integer&nbsp;<code>k<\/code>.<\/p>\n\n\n\n<p>We call some integer&nbsp;<strong>wonderful<\/strong>&nbsp;if it is a&nbsp;<strong>permutation<\/strong>&nbsp;of the digits in&nbsp;<code>num<\/code>&nbsp;and is&nbsp;<strong>greater in value<\/strong>&nbsp;than&nbsp;<code>num<\/code>. There can be many wonderful integers. However, we only care about the&nbsp;<strong>smallest-valued<\/strong>&nbsp;ones.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, when&nbsp;<code>num = \"5489355142\"<\/code>:<ul><li>The 1<sup>st<\/sup>&nbsp;smallest wonderful integer is&nbsp;<code>\"5489355214\"<\/code>.<\/li><li>The 2<sup>nd<\/sup>&nbsp;smallest wonderful integer is&nbsp;<code>\"5489355241\"<\/code>.<\/li><li>The 3<sup>rd<\/sup>&nbsp;smallest wonderful integer is&nbsp;<code>\"5489355412\"<\/code>.<\/li><li>The 4<sup>th<\/sup>&nbsp;smallest wonderful integer is&nbsp;<code>\"5489355421\"<\/code>.<\/li><\/ul><\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>minimum number of adjacent digit swaps<\/strong>&nbsp;that needs to be applied to&nbsp;<\/em><code>num<\/code><em>&nbsp;to reach the&nbsp;<\/em><code>k<sup>th<\/sup><\/code><em><strong>&nbsp;smallest wonderful<\/strong>&nbsp;integer<\/em>.<\/p>\n\n\n\n<p>The tests are generated in such a way that&nbsp;<code>k<sup>th<\/sup><\/code>&nbsp;smallest wonderful integer exists.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> num = \"5489355142\", k = 4\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> The 4<sup>th<\/sup> smallest wonderful number is \"5489355421\". To get this number:\n- Swap index 7 with index 8: \"5489355142\" -&gt; \"5489355412\"\n- Swap index 8 with index 9: \"5489355412\" -&gt; \"5489355421\"\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 = \"11112\", k = 4\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> The 4<sup>th<\/sup> smallest wonderful number is \"21111\". To get this number:\n- Swap index 3 with index 4: \"11112\" -&gt; \"11121\"\n- Swap index 2 with index 3: \"11121\" -&gt; \"11211\"\n- Swap index 1 with index 2: \"11211\" -&gt; \"12111\"\n- Swap index 0 with index 1: \"12111\" -&gt; \"21111\"\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 = \"00123\", k = 1\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> The 1<sup>st<\/sup> smallest wonderful number is \"00132\". To get this number:\n- Swap index 3 with index 4: \"00123\" -&gt; \"00132\"\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= num.length &lt;= 1000<\/code><\/li><li><code>1 &lt;= k &lt;= 1000<\/code><\/li><li><code>num<\/code>&nbsp;only consists of digits.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Next Permutation + Greedy<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(k*n + n^2)<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++\">\nclass Solution {\npublic:\n  int getMinSwaps(string s, int k) {\n    string t(s);\n    while (k--) next_permutation(begin(t), end(t));\n    const int n = s.length();\n    int ans = 0;\n    for (int i = 0; i < n; ++i) {\n      if (s[i] == t[i]) continue;\n      for (int j = i + 1; j < n; ++j) {\n        if (s[i] != t[j]) continue;\n        ans += j - i;\n        t = t.substr(0, i + 1) + t.substr(i, j - i) + t.substr(j + 1);\n        break;\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a string&nbsp;num, representing a large integer, and an integer&nbsp;k. We call some integer&nbsp;wonderful&nbsp;if it is a&nbsp;permutation&nbsp;of the digits in&nbsp;num&nbsp;and is&nbsp;greater in value&nbsp;than&nbsp;num.&#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":[88,177,121,4],"class_list":["post-8436","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-medium","tag-permutation","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8436","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=8436"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8436\/revisions"}],"predecessor-version":[{"id":8438,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8436\/revisions\/8438"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8436"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8436"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8436"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}