Class Solution
java.lang.Object
g1801_1900.s1850_minimum_adjacent_swaps_to_reach_the_kth_smallest_number.Solution
1850 - Minimum Adjacent Swaps to Reach the Kth Smallest Number.<p>Medium</p>
<p>You are given a string <code>num</code>, representing a large integer, and an integer <code>k</code>.</p>
<p>We call some integer <strong>wonderful</strong> if it is a <strong>permutation</strong> of the digits in <code>num</code> and is <strong>greater in value</strong> than <code>num</code>. There can be many wonderful integers. However, we only care about the <strong>smallest-valued</strong> ones.</p>
<ul>
<li>For example, when <code>num = "5489355142"</code>:
<ul>
<li>The 1<sup>st</sup> smallest wonderful integer is <code>"5489355214"</code>.</li>
<li>The 2<sup>nd</sup> smallest wonderful integer is <code>"5489355241"</code>.</li>
<li>The 3<sup>rd</sup> smallest wonderful integer is <code>"5489355412"</code>.</li>
<li>The 4<sup>th</sup> smallest wonderful integer is <code>"5489355421"</code>.</li>
</ul>
</li>
</ul>
<p>Return <em>the <strong>minimum number of adjacent digit swaps</strong> that needs to be applied to</em> <code>num</code> <em>to reach the</em> <code>k<sup>th</sup></code> <em><strong>smallest wonderful</strong> integer</em>.</p>
<p>The tests are generated in such a way that <code>k<sup>th</sup></code> smallest wonderful integer exists.</p>
<p><strong>Example 1:</strong></p>
<p><strong>Input:</strong> num = “5489355142”, k = 4</p>
<p><strong>Output:</strong> 2</p>
<p><strong>Explanation:</strong> The 4<sup>th</sup> smallest wonderful number is “5489355421”. To get this number:</p>
<ul>
<li>
<p>Swap index 7 with index 8: “5489355142” -> “5489355412”</p>
</li>
<li>
<p>Swap index 8 with index 9: “5489355412” -> “5489355421”</p>
</li>
</ul>
<p><strong>Example 2:</strong></p>
<p><strong>Input:</strong> num = “11112”, k = 4</p>
<p><strong>Output:</strong> 4</p>
<p><strong>Explanation:</strong> The 4<sup>th</sup> smallest wonderful number is “21111”. To get this number:</p>
<ul>
<li>
<p>Swap index 3 with index 4: “11112” -> “11121”</p>
</li>
<li>
<p>Swap index 2 with index 3: “11121” -> “11211”</p>
</li>
<li>
<p>Swap index 1 with index 2: “11211” -> “12111”</p>
</li>
<li>
<p>Swap index 0 with index 1: “12111” -> “21111”</p>
</li>
</ul>
<p><strong>Example 3:</strong></p>
<p><strong>Input:</strong> num = “00123”, k = 1</p>
<p><strong>Output:</strong> 1</p>
<p><strong>Explanation:</strong> The 1<sup>st</sup> smallest wonderful number is “00132”. To get this number:</p>
<ul>
<li>Swap index 3 with index 4: “00123” -> “00132”</li>
</ul>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>2 <= num.length <= 1000</code></li>
<li><code>1 <= k <= 1000</code></li>
<li><code>num</code> only consists of digits.</li>
</ul>
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
Solution
public Solution()
-
-
Method Details
-
getMinSwaps
-