Bigger is Greater

In this problem i will explain the following problem taken from hackerrank.com

Lexicographically greater means that suppose if we were to arrange these words on a dictionary than s should come just after w.

We will use the word "mekhfa" in our example.

m

e

k

h

f

a

The key observation in this algorithm is that when we want to compute the next word  in a dictionary "s" such that it contains all the letters as "w" OR equivalently when we want to compute the next permutation of the word "w", we must “increase” the sequence as little as possible. Just like when we count up using numbers, we try to modify the rightmost elements and leave the left side alone (ex. if we want to fin the next permutation of the number 234 we would start from the right most element rather than the first element).

Similarly here also we will start from the end and find the largest sub-string that is non-increasing, non increasing means string[i-1] > string[ i ],  in our case it's  

k

h

f

a

This sub-string is already in the highest permutation, so we can’t make a next permutation just by modifying it – we need to modify some element(s) to the left of it.

Now, look at the element immediately to the left of the index of "k" (in the example it’s "e") and call it the pivot. (If there is no such element – i.e. the entire sequence is non-decreasing – then this is already the last permutation.) The pivot is necessarily less than the head of the sub-string (in the example it’s "k"). So some element in the sub-string is greater than the pivot. If we swap the pivot with the smallest element in the sub-string that is greater than the pivot ("f" in our case), then the beginning (i.e. m, f ) of the string is minimized. (The string is everything in the sequence except for the new sub-string. i.e.

k

h

e

a

 (Note that if the sub-string has multiple copies of the new pivot, we should take the rightmost copy – this plays into the next step.)

Finally, we sort the sub-string in non-decreasing (i.e. weakly increasing) order because we increased the prefix, so we want to make the new suffix as low as possible. In fact, we can avoid sorting and simply reverse the suffix, because the replaced element respects the weakly decreasing order. So finally, we get the sequence 

m

f

a

e

h

k

which is the next permutation that we wanted.

Here are the steps.

1. Start from the end and find the index i such that string[ i ] < string[ i +1].
2. The element at index i (i.e. string[ i ] ) is called pivot. Now Search the elements with index > i  and find the element which is next greater than string[ i ] . Let say we find the element at index  j to be next greater than string[ i ] .
3. Swap string [ j ] and string[ i ].
4. Reverse Or sort the sub-string starting at string[ i+1] .

Here is my code for reference.

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

    int t;

    cin>>t;

  for (int i = 0; i < t; i++){ 

            string s;

            cin >> s;

            int n = s.length();

            int j, k;

            for (j = n - 2; j >= 0; j--) {  /* initializing j which is pointing to element at index n-2 */

                    for (k = n - 1; k > j && s[k] <= s[j]; k--);  /* finding the largest non-increasing sub-string */

                    if (k == j) continue;

                    char tmp = s[k]; 

                    s[k] = s[j];

                    s[j] = tmp;   /* swaping the elements */

                    sort(s.begin() + j + 1, s.end()); /* sorting the sub-string */

                    break;

            }

            if (j < 0) cout << "no answer" << endl;  /* if  no permutation exist than this will get executed */

            else  cout << s << endl;  /* if permutation exist than print it */

    }

    return 0;

}

*****

IF YOU WANT ME TO EXPLAIN A PERTICULAR PROBLEM THAN PLEASE LEAVE A LINK TO THE PROBLEM IN THE COMMENT SECTION

*****