Bigger is Greater : Challenge | Strings | Algorithms | HackerRank

Bigger is Greater : Challenge | Strings | Algorithms | HackerRank
Given a word w, rearrange the letters of w to construct another word s in such a way that s is lexicographically greater than w. In case of multiple possible answers, find the lexicographically smallest one.

We can find the next largest lexicographic string for a given string S using the following step.

Iterating over every character, we will get the last value i (starting from the first character) that satisfies the given condition

S[i] < S[i + 1]

Now, we will get the last value j such that

S[i] < S[j]

We now interchange S[i] and S[j]. And for every character from i+1 till the end, we sort the characters. i.e.,

sort(S[i+1]..S[len(S) - 1])

The given string is the next largest lexicographic string of S.

One can also use next_permutation function call in cpp.

https://codepair.hackerrank.com/paper/dSn8pZvz?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
static String nextPermutation(String word){
char[] letters = word.toCharArray();
int k=-1,l=-1;
for(int i=letters.length-2;i>=0;i--){
if(letters[i]<letters[i+1]){
k=i;
break;
}
}
if(k==-1)
return "no answer";
for(int i=letters.length-1;i>k;i--){
if(letters[i]>letters[k]){
l=i;
break;
}
}
char temp = letters[k];
letters[k] = letters[l];
letters[l] = temp;
char[] newWord = new char[letters.length];
for(int i=0;i<k+1;i++){
newWord[i]=letters[i];
}
int j=1;
for(int i=letters.length-1;i>k;i--){
newWord[k+j]=letters[i];
j++;
}
return new String(newWord);
}

Same as leetcode next permutation:
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
http://massivealgorithms.blogspot.com/2014/06/yus-coding-garden-leetcode-question-61.html
http://massivealgorithms.blogspot.com/2014/07/leetcode-next-permutation-darrens-blog.html
Read full article from Bigger is Greater : Challenge | Strings | Algorithms | HackerRank