minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given a string <code>num</code> representing the digits of a very large integer and an integer <code>k</code>. You are allowed to swap any two adjacent digits of the integer at most <code>k</code> times.

Return the minimum integer you can obtain also as a string.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/17/q4_1.jpg" style="width: 500px; height: 40px;" />
<pre>
Input: num = &quot;4321&quot;, k = 4
Output: &quot;1342&quot;
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.
</pre>

Example 2:

<pre>
Input: num = &quot;100&quot;, k = 1
Output: &quot;010&quot;
Explanation: It&#39;s ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.
</pre>

Example 3:

<pre>
Input: num = &quot;36789&quot;, k = 1000
Output: &quot;36789&quot;
Explanation: We can keep the number without any swaps.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= num.length &lt;= 3 * 104</code></li>
	<li><code>num</code> consists of only digits and does not contain leading zeros.</li>
	<li><code>1 &lt;= k &lt;= 109</code></li>
</ul>

第 196 场周赛

weekly-contest-196

minInteger

首席工程师

Minimum Possible Integer After at Most K Adjacent Swaps On Digits

Greedy

Binary Indexed Tree

Segment Tree

String

给定一个字符串&nbsp;<code>num</code> 表示非常大的整数和一个整数 <code>k</code>。你可以交换这个整数相邻数位的数字 最多&nbsp;<code>k</code>&nbsp;次。

请你返回你能得到的最小整数，并以字符串形式返回。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2020/06/17/q4_1.jpg" style="height:40px; width:500px" />

<pre>
输入：num = "4321", k = 4
输出："1342"
解释：4321 通过 4 次交换相邻数位得到最小整数的步骤如上图所示。
</pre>

示例 2：

<pre>
输入：num = "100", k = 1
输出："010"
解释：输出可以包含前导 0 ，但输入保证不会有前导 0 。
</pre>

示例 3：

<pre>
输入：num = "36789", k = 1000
输出："36789"
解释：不需要做任何交换。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= num.length &lt;= 3 * 104</code></li>
	<li><code>num</code>&nbsp;只包含&nbsp;数字&nbsp;且不含有&nbsp;前导 0&nbsp;。</li>
	<li><code>1 &lt;= k &lt;= 109</code></li>
</ul>