See the original problem on HackerRank.
This problem requires to find the smallest permutation of the input string that is also bigger than the input string.
This is a classical problem in Computer Science (in mathematics, in general) and often it’s referred as finding the “next permutation in lexicographic ordering”.
The method consists in:
- find the largest index \( i \) such that \( a[i] < a[i + 1] \). If no such index exists, the permutation is the last permutation;
- find the largest index \( j \) greater than \( i \) such that a[i] < a[j];
- swap the value of \( a[i] \) with that of \( a[j] \);
- reverse the sequence from \( a[i + 1] \) up to and including the final element of the sequence.
This algorithm is generic and works for any type of sequence, provided that a lexicographical order exists for that sequence.
We can transform the words into C++ code quite easily and step by step:
Actually, the algorithm above is already in the C++ standard library and it’s known as
next_permutation. So we can write down:
However, this exercise is very useful because it lets us find the solution ourselves and dig into these concepts.