This was helpful. Thanks!

very nice solution

good logic !!!

Try to solve in Java. Calculating all next lexicographical permutation using this logic. But Test#1, #2 says 4s Terminated due to time out. Any suggestion?

Too helpful! Thanxx! :-)

Helped :)

Super helpful! Learned something new today!

Nice and clear explanation!

thanks!! that was well explained

Best Explanantion! Learned something new!

very helpful, thanks

Thank you. This was so helpful and very cool.

wow! great explanation ,Thanks

Thank You! Something new everyday.

That was really helpful!! Got to learn a lot..thanks :)

great

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;


int main() {
    long long int t;
    cin>>t;
    while(t>0)
    {
        string s;
        cin>>s;
        string ss=s;
        int i=s.length()-1;
        int pivot;
        while(s[i-1]>=s[i]&&i>=0)
            i--;
        if(i!=0)
          {
            pivot=i-1;
            int min=INT_MAX;
            int index;
            for(int j=i;j<s.length();j++)
              {
                if(int(s[j])>int(s[pivot])&&min>int(s[j])){
                    min=s[j];
                    index=j;
                }
            }
           char temp=s[pivot];
            s[pivot]=s[index];
            s[index]=temp;
            sort(s.begin()+i,s.end());
            cout<<s<<endl;
        }
        else
            cout<<"no answer\n";
         t--;    
    }
        
    return 0;
}

In my code,testcase 1 and testcase 2 are showing segmentation fault can you tell me what is the reason.I have used the same concept as described in article.

Guys think about the logic for a few minutes before looking at this!

Great Tutorial

extremely helpful! thanks a lot!

thank you very much

I tried to implement same algorithm. But only got test0 and test3 successful. I have written following code. Where might I be wrong?

public static void main(String[] args) throws IOException{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); 
    int n = Integer.parseInt(br.readLine());
    String[] str = new String[n];
    for (int i =0; i<n;i++){
        str[i]=br.readLine();
    }
    //int n=6;
    //String[] str = {"ab","bb","hefg","dhck","dkhc","zzzayybbaa"};
    List<String> pLst=new ArrayList<String>();
    for(String s:str){
        char[] chars = s.toCharArray();
        List<Character> lst =toChList(chars);
        pLst.add(listToString(nextBigPerm(lst)));
    }
    for(int i=0;i<str.length;i++){
        System.out.println((pLst.get(i).equals(str[i]) || str[i].length()<2)?"no answer":pLst.get(i));
    }
}
private static List<Character> toChList(char[] chars){
    List<Character> ch = new ArrayList<Character>();
    for (char c: chars)
        ch.add(c);
    return ch;
}
private static List<Character> nextBigPerm(List<Character> lst){
    int pivot = 0;
    int swap = lst.size() - 1;
    if (swap ==0) return lst;
    for(int i=1;i<lst.size();i++){
        if (lst.get(i-1)<lst.get(i))
            pivot=i-1;
        if (lst.get(pivot)<lst.get(i))
            swap = i;
    }
    Collections.swap(lst,pivot,swap);
    Collections.sort(lst.subList(pivot+1,lst.size()));
    return lst;
}
private static String listToString(List<Character> lst){
    StringBuilder s = new StringBuilder();
    for(Character c:lst)
        s.append(c);
    return s.toString();
}

Thanks @devstarj this http://www.nayuki.io/page/next-lexicographical-permutation-algorithm could be posted in the topics for Java solution

Awesome! Love the hackerrank community.

very nice

Thanks it was very helpful

I love you

Thank you ...

Thanks for the logic! Great help.

for _ in range(int(input())):
    s = input()
    has_greater = False
    for i in range(len(s)-1)[::-1]:
        if ord(s[i]) < ord(s[i+1]):
            for j in range(i+1,len(s))[::-1]:
                if ord(s[i]) < ord(s[j]):
                    lis = list(s)
                    lis[i],lis[j]=lis[j],lis[i]
                    print("".join(lis[:i+1]+lis[i+1:][::-1]))
                    has_greater = True
                if has_greater == True:
                    break
        if has_greater == True:
            break
    if has_greater == False:
        print("no answer")

thanks for posting this algorithm. here's a python 3 solution based on this algorithm

this is a hell of a lot simpler then the nayuki page

http://stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string

Thanks a Lot.I didnt think that it is this much simple

Learnt new logic. Very helpful. Thanks!

That moment when your inital algorithm was exactly the same

Thank you so much.It really helped a lot.

Thank you so much!

Also remember to include the edge case where the length of the word is 1.

(logic==excellent)?U R grt:U R malekith;

yeah !!! that taught me the algo!! thanks!1

Thank you so much!

Word up cuh, much respeck much respeck.

I think there is problem in the algorithm, instead of reversing the subarray , it should be sorted.

good job,better than editorial!

nice one

Thanks for the blog

thanks. copied this solution and refactored a little bit.

    static String biggerIsGreater(String w) {
        char[] chars = w.toCharArray();
        return nextPermutation(chars)
            ? new String(chars)
            : "no answer";
    }
    static boolean nextPermutation(char[] array) {
        int i = getLastPeakIndex(array);
        if (i <= 0) // like "dcba", no answer
            return false;

        int j = getReplacementIndex(array, i - 1);

        swap(array, i-1, j);

        // Reverse the part on the right of i - 1 to make it as small as possible
        j = array.length - 1;
        while (i < j) {
            swap(array, i, j);
            i++;
            j--;
        }
        
        return true;
    }

    static int getLastPeakIndex(char[] chars){
        int i = chars.length - 1;
        while (i > 0 && chars[i - 1] >= chars[i])
            i--;
        return i;
    }

    static int getReplacementIndex(char[] chars, int givenIndex){
        int i = chars.length - 1;
        while (chars[i] <= chars[givenIndex])
            i--;
        return i;
    }

    static void swap(char[] chars, int a, int b){
        chars[a] ^= chars[b];
        chars[b] ^= chars[a];
        chars[a] ^= chars[b];
    }

thanks bro!! helpful..

thank so much :))

Thanks for your Algorithm, it is very helpful. Exploring new algorithms always feels great.

Hi,

I have created a tutorial for you all. have a look, i hope it will help you to solve the problem.

Here is the video explanation of my solution in O(n) time -

https://youtu.be/BMbeeB_57Pk

After writing my (probably overly complex, BUT working) solution, I was pretty shocked to find out that next_permuation() exists. Haha. I will definitely be using that in the future though.

Thanks man!! Your comment got me to try that problem again.. :)

this prompted me to write a proper solution!

It all evens out because we don't have a big int class

The point is to write your own implementation and not use built-in functions for everything. Of course it's easy if you don't have to think..

Why this assault gets so many upvotes?

yes that is stupid, but you can take line by line and test it.

I used git diff on current and expected outputs in that case.

THx a lot man!! So useful for me!!!

So cool man!!! Just miss a "=" sign somewhere.

thanks alot...yarr this testcase is very useful..

Thanks!!

I had yours working correctly, but failing for "9357742" which my algo gave 94.... and the correct should be 9372457

Thanks a lot... It is insanely hard to find such a bug from those gigantic inputs.

thanks a ton buddy :)

thanks!

WOW dude!! Only if i had swapped, this error wouldnt have been encountered itself... Thanks for the help!!

Thanks a lot bro only that little equal to sign was missing which solved everything.And got all submitted.

Nice :)

Helped me !

Thanks! :D

thanks man!

Sir...hello!!!In case of single letter strings my output is "no answer". but i'm getting remark saying.."segmentation fault" can u please help me...

That was killing me. Thanks, man/woman.

no use!!

thanks bro i was printing the same 1 letter string for that im=nstead of no answer .

Thank you so much. This helped my java solution pass test cases 1 and 2. At first, I thought my issue was that I was using a linear search to find the location to swap instead of a binary search. Even after I implemented the binary search, I timed out. Instead, it was an incomplete understanding of outputing to the standard output that got me. Changing the outputing method to use the OutputStreamWriter changed the runtime for test cases 1 and 2 from both over 4 seconds to just about 1 second.

This post should be higher up.

I did exactly the same. And it works but, its complex. my version is even more complex. you actually dont need double for loop.

for (int j = len - 2; j >= 0; --j) {
    if (chars[j] < chars[j + 1]) {
        ind = j;
        break;
    }
}

Then swap and sort.

I deciphered it the same way, but with this logic only TC1 passes rest all fails.

Thanks man...wonderful logic

I am using the same logic but it is working only for test case 0 can some one help me find out what is wrong long int t; int l,m,i,j;

scanf("%ld ",&t);
char ch[101],c;
while(t>=1)
    {
    scanf("%s",ch);
    l=strlen(ch)-1;
    i=l+1;
    do
    {
        i--;
        if(i==0)
            break;
    }while(ch[i]<=ch[i-1]);
    if(i!=0)
    {
    m=i;
    while(m<=l)
        {
        if(ch[m]<ch[i-1])
            break;
        m++;
    }
        m--;
        c=ch[m];
        ch[m]=ch[i-1];
        ch[i-1]=c;
        for(m=l;m>=i+1;m--)
        {
            for(j=i;j<m;j++)
            {
            if(ch[j]>ch[j+1])
                {
                c=ch[j];
                ch[j]=ch[j+1];
                ch[j+1]=c;
            }
           }
        }
     for(i=0;i<=l;i++)
         printf("%c",ch[i]);
    }
    else
        printf("no answer");
    printf("\n");
    t--;
}

What is sort()?

i have done the exact same thing but first 3 cases are giving wrong answer and i can't find where since the input is too big

actually you don't need to "sort everything right of this position", just reverse it, since it is naturelly descending

i used to same logic but it is showing incorrect for case no 1,2,3

I approached the problem in a similar way