# 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.

We've worked on this challenge in these gyms: modena