Abstract / Summary

Given a number as a string and an integer k, find the minimum adjacent swaps needed to turn it into the kth smallest number possible by rearranging its digits.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 72% (40k+ submissions).

Typical patterns to solve this problem:

• Greedy
• String
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method getMinSwaps that computes the minimum number of adjacent swaps required to transform a given numeric string num into its k-th lexicographically greater permutation. The algorithm proceeds in two distinct phases: first it generates the target permutation by repeatedly applying std::next_permutation; second it aligns the original string with this target by performing left-rotations that correspond to a series of adjacent swaps, accumulating the total number of swaps performed.

Finding the k-th permutation

The method begins by creating a mutable copy of the input string named wonderful. A loop executes k times, each iteration invoking std::next_permutation on the copy. This standard library routine rearranges the characters of the string into the next lexicographically larger ordering, or leaves the sequence unchanged if it is already the greatest permutation. By iterating exactly k times, the code arrives at the k-th permutation relative to the original ordering.

auto wonderful = num;
while (k--)
    std::next_permutation(wonderful.begin(), wonderful.end());

The comment in the source highlights the convenience of next_permutation compared with manual permutation generation, emphasizing that the library function handles the combinatorial logic internally.

Aligning the original string

After the target permutation is obtained, the algorithm scans both strings in parallel to locate positions where the characters differ. For each mismatched index same, it searches forward in the original string num to find the first occurrence of the character that should appear at that position according to wonderful. The search starts just after the current index to ensure that only later characters are considered, preserving the relative order of already aligned characters.

for (size_t same = 0; same < num.size(); same++)
    if (num[same] != wonderful[same])
    {
        auto scan = num.find(wonderful[same], same + 1);
        std::rotate(num.begin() + same, num.begin() + scan, num.begin() + scan + 1);
        result += scan - same;
    }

When the required character is located at position scan, the code performs a left-rotation of the sub-range [same, scan]. The rotation moves the character at scan to index same while shifting all intervening characters one position to the right. This operation is equivalent to a series of adjacent swaps, and the number of swaps contributed by this step is precisely scan - same. The variable result aggregates these counts, yielding the total minimum swaps needed to reach the target permutation.

Edge conditions handled

The algorithm implicitly handles several edge conditions without explicit branching:

• If k is zero, the while loop that generates the target permutation does not execute, leaving wonderful identical to num. Consequently, the subsequent comparison loop finds no mismatches, and the method returns zero swaps.
• When the original string is already the greatest permutation, further calls to std::next_permutation leave the string unchanged. Repeating this operation k times still produces a valid target (the same string), and the swap counting phase again results in zero.
• The find call searches only beyond the current index, guaranteeing that a matching character will be found because wonderful is a permutation of num. This ensures that the rotation step always has a valid range to operate on.
• The rotation operation works correctly even when scan equals same + 1. In that case, the range consists of two adjacent characters, and the rotation reduces to a single adjacent swap, correctly adding one to the result.

Performance considerations

The code leverages the efficiency of the standard library in two ways. First, std::next_permutation runs in linear time relative to the length of the string and performs the minimal number of element moves needed to reach the next ordering. By invoking it k times, the algorithm avoids the combinatorial explosion that would arise from generating all permutations explicitly.

Second, the alignment phase uses std::string::find to locate the required character, which scans forward from a given position. Although this is a linear search, each character is examined at most once across all iterations because once a character is moved into its correct place, it will never be scanned again. The subsequent std::rotate call operates on a contiguous sub-range and is implemented using three reverse operations, each linear in the size of the range. The total work performed by all rotations equals the sum of distances each character travels, which matches the minimal number of adjacent swaps required. Consequently, the overall runtime scales proportionally to the length of the string and the number of swaps, providing an efficient solution for the problem constraints.

Imagine you have a row of wooden blocks with numbers painted on them. Your goal is to change the order of these blocks to make a new number. You are given a magic wand that can rearrange all the blocks to create the very next biggest number possible. You wave this wand a specific number of times to reach a target arrangement of blocks.

Once you know where all the blocks should be, you look at your messy row of blocks and compare it to the goal row. You look at the first spot to see if the block there matches the block in the goal row. If the blocks do not match, you find the right block hidden somewhere else in your row and move it to the front. You keep doing this for every single spot along the row until your blocks look exactly like the target row. Every time you move a block, you count the step as one tiny piece of work. By the time you finish moving all the blocks, you have a final tally of how many moves were made to get everything in the right place.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python	TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java		Go	Python	TS
	Progiez	C++		Java			Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	haoel	C++
	JoshCrozier		JS
	suxrobGM				C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality