Bigger is Greater

See the original problem on HackerRank.

Solutions

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:

1. find the largest index \( i \) such that \( a[i] < a[i + 1] \). If no such index exists, the permutation is the last permutation;
2. find the largest index \( j \) greater than \( i \) such that a[i] < a[j];
3. swap the value of \( a[i] \) with that of \( a[j] \);
4. 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 1. find the last i+1 so that: s[i+1] > s[i]
auto iplusone = adjacent_find(s.rbegin(), s.rend(), greater<>{});

// 1. bis: if it does not exist -> the sequence is already the greatest one
if (iplusone==s.rend())
{
    cout << "no answer" << endl;
    return;
}

auto i = next(iplusone); // it's reverse iterator (it "goes back" to i)
const auto x = *i;
// 2. find the last j so that: s[j] > s[i]
auto j = find_if(s.rbegin(), i, [=](char c){
   return c > x;
});

// 3. swap s[i] and s[j]
swap(*i, *j);

// 4. reverse the sequence from s[i+1] up to the end
// note: we reverse from the end of the sequence to s[i] excluded (that is s[i+1] included, as required)
reverse(s.rbegin(), i);
cout << s << endl;

Actually, the algorithm above is already in the C++ standard library and it’s known as next_permutation. So we can write down:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// if already the last one
if (next_permutation(begin(s), end(s)) == false)
{
    cout << "no answer" << endl;
}
else 
{
    // next_permutation changes s in-place
    cout << s << endl;
}

However, this exercise is very useful because it lets us find the solution ourselves and dig into these concepts.