# Bigger is Greater

# Bigger is Greater

devstarj + 53 comments Here is a good explanation of a next lexicographical permutation algorithm:

http://www.nayuki.io/page/next-lexicographical-permutation-algorithm

EliottG + 0 comments This was helpful. Thanks!

sanrsk + 0 comments very nice solution

surya_b800 + 0 comments good logic !!!

Nugjii + 5 comments 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?

christina_ytang + 3 comments test the case when input is just one letter (e.g. p), the output should be "no answer". This solved my problem.

biswajit16 + 0 comments [deleted]aashirwadgarg + 2 comments no it didn't solved

zaverichintan5 + 0 comments first of all check if same letters are repeating

vikybas + 0 comments thanks, it solved my problem.

thuanbao + 3 comments Try to use

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

to read the input. It has 100000 test cases so Scanner won't work

sonu628 + 1 comment can you please tell how to BufferReader to scan multiple lines of Strings with Exception Handling

thuanbao + 3 comments here is what i did:

BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int num = Integer.parseInt(in.readLine()); String line = ""; for (int i = 0; i < num; i++) { line = in.readLine(); // Do your stuff here }

sonu628 + 0 comments Thanks buddy

alex_sde + 1 comment didn't work, i still get timeouts

shraiysh + 1 comment I did this.. Lengthy but worked.

import java.util.*; class Solution { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); for(int test=1;test<=t;test++) { String s=sc.next(),a=""; int numberCharsTaken; int flag = 0,x=0; for(numberCharsTaken = 1;numberCharsTaken<=s.length();numberCharsTaken++) { a = s.substring(s.length() - numberCharsTaken); for(x = a.length()-1;x>0;x--) { if(a.charAt(0)<a.charAt(x)) { flag = 1; break; } if(flag == 1) break; } if(flag == 1) break; } if(flag == 1){ String temp = a.substring(0,x)+a.substring(x+1); char c[] = temp.toCharArray(); Arrays.sort(c); temp = a.charAt(x) + new String(c); String ans = s.substring(0,s.length()-numberCharsTaken)+temp; System.out.println(ans); } else System.out.println("no answer"); } } }

shreeshakedilaya + 0 comments @shraiysh Can you explain the logic here. The lexicographical permutation solution didnt work for me. It is giving me runtime error. But your code is working for me. I dont understand why.

rongbino + 0 comments It did not work. It stuck in line 20348

avishekde + 0 comments Scanner will work in these cases. I submitted using scanner. The problem must lie elsewhere.

Socrot + 0 comments thanks! that is what I needed. Don't really know why Scanner is slower than buffreader though.

kumarnikhil14997 + 0 comments [deleted]kumarnikhil14997 + 0 comments ## Simple java solution : algorithm n wikipedia

static String biggerIsGreater(String w) { char[] arr = w.toCharArray(); int i = arr.length - 1; // finding p --> i while(i>0 && arr[i-1]>=arr[i]){ i--; } if(i<=0){ //System.out.println("Pretty much last one!!"); return "no answer"; } int j = arr.length-1; while(arr[j]<= arr[i-1]){ j--; } char temp = arr[i-1]; arr[i-1] = arr[j]; arr[j] = temp;

`j = arr.length - 1; while(i<j) { char tem = arr[i]; arr[i] = arr[j]; arr[j] = tem; j--; i++; } String ret = new String(arr); return ret; }`

OrcaKnowsBest + 0 comments Use this to find no answer without solving:

https://www.hackerrank.com/challenges/bigger-is-greater/forum/comments/595411

kiner_shah + 1 comment Too helpful! Thanxx! :-)

biswajit16 + 0 comments hey i have used the same logic and implemented this problem.however my code fails for test case 1 and 2 .can u please review my code and tell where the error lies?? i posted my code in the discussions forum.please have a look at the recent comments with my username.

Surbhi94 + 0 comments Helped :)

dlyu1101 + 0 comments Super helpful! Learned something new today!

nischalgprasad + 0 comments Nice and clear explanation!

manjiri + 0 comments thanks!! that was well explained

aleenaannajames9 + 0 comments Best Explanantion! Learned something new!

doanhuunoi + 0 comments very helpful, thanks

lafreniere_dj + 0 comments Thank you. This was so helpful and very cool.

ibrahim_galion + 0 comments wow! great explanation ,Thanks

hucraig + 0 comments [deleted]shruti95 + 0 comments Thank You! Something new everyday.

parnika182 + 0 comments That was really helpful!! Got to learn a lot..thanks :)

anubhavaron00001 + 0 comments great

chandra130313 + 4 comments #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.

MinhVu + 1 comment Hi,

I have a confuse about this algorithm. In this tutorial, they said the suffix is 5 3 3 0 and the pivot is 2. After that, they said we can swap 2 with the smallest number, in the suffix that is greater than pivot. I misunderstood in here why 0 1 3 is the minimize prefix? In my opinion, 0 1 0 is the minimum prefix, right? Could you guys explain that point for me please. Thanks

Trishla08 + 1 comment Hi, the pivot should be smaller than the number you are swapping with, otherwise the final sequence would be lexicographically smaller than the original. So, we are finding the smallest number in the suffix, greater than the pivot, which is 3 in the tutorial. Hope that helped.

ritik042 + 0 comments In your first while loop you are using condition i>=0, which results in i=-1 if its already sorted string. So your next condition becomes s[-1]<=s[0] which is resulting in segementation fault.

alur_pawan + 0 comments Hmm, I looked at your code, and incase you havent figured it out yet, you get segmentation fault beacuse you are accessing s[i-1] when i is 0; Check for this and fix it to get rid of segmentation fault

chandlermd + 0 comments I was having the same problem....I found the error to be in the provided code (not the first time). Try adding a "free(w);" at the end of the loop in main. The sandbox was running out of memory!

zombieSlayer37 + 0 comments Guys think about the logic for a few minutes before looking at this!

rajvineet90 + 0 comments Great Tutorial

hengjoekit + 0 comments extremely helpful! thanks a lot!

pavneet_singh + 0 comments [deleted]linuxr + 0 comments thank you very much

dprabin + 1 comment 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(); }`

SameerRaj + 0 comments Try checking is the next permutated string is actually greater than the original string or not. Try if(next_str.equals(str)||next_str.compareTo(str)<1)System.out.println("no answer"); permutated string=next_str original=string Now if the permutated string compareTo original string is smaller then print "no answer" because it is actually smaller than the original string. It happens when pivot=swap=0 means rest of the characters are already smaller.

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

daviddecoding + 0 comments Awesome! Love the hackerrank community.

ashariduttparas1 + 0 comments very nice

himanshu0929y + 0 comments Thanks it was very helpful

lsoyul + 0 comments I love you

nibin + 0 comments Thank you ...

juhiduseja + 0 comments Thanks for the logic! Great help.

randy_y_yuan + 3 comments 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

rilwan03 + 0 comments no need check

*ord(s[i]) < ord(s[j])*, just*s[i] < s[j]*is enough.yang_4978 + 0 comments [deleted]dm_dubovitsky + 0 comments this code like in C

Would rather use more Pythonic style, for example:

def biggerIsGreater(s):

`for i in range(len(s)-1)[::-1]: if s[i] < s[i+1]: for j in range(i+1,len(s))[::-1]: if s[i] < s[j]: lis = list(s) lis[i],lis[j]=lis[j],lis[i] return "".join(lis[:i+1]+lis[i+1:][::-1]) return 'no answer'`

bheaps + 1 comment this is a hell of a lot simpler then the nayuki page

prakharsinha2808 + 0 comments [deleted]

nithya_smiley + 0 comments Thanks a Lot.I didnt think that it is this much simple

agarwal1810 + 0 comments Learnt new logic. Very helpful. Thanks!

daniyark + 0 comments That moment when your inital algorithm was exactly the same

saichaitanya080 + 0 comments Thank you so much.It really helped a lot.

ashwin0825 + 0 comments Thank you so much!

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

bhavikgevariya + 0 comments (logic==excellent)?U R grt:U R malekith;

anshumanc007 + 0 comments yeah !!! that taught me the algo!! thanks!1

khue0975858572 + 0 comments Thank you so much!

maxballard333 + 0 comments Word up cuh, much respeck much respeck.

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

tieros + 0 comments It's same with sorting. In algorith page it says :"Firstly, identify the longest suffix that is non-increasing (i.e. weakly decreasing)." And that's the part helped me to see my algorithm's mistake. I was just finding the pair to swap, then sorting second part. It was giving correct answers for only around 96 percent of words, then looking for alternative permutations was causing timeouts.

plt1999 + 0 comments good job,better than editorial!

gandhi_rachuputi + 0 comments nice one

pramodprajapati1 + 0 comments Thanks for the blog

duoduoxia + 0 comments 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]; }

andreabonvini + 0 comments [deleted]vaibhavch9876 + 0 comments [deleted]rajukumarnitp + 0 comments thanks bro!! helpful..

pdhoang91 + 0 comments thank so much :))

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

Kanahaiya + 0 comments 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 -

ympb121 + 8 comments All of this C++ next_permutation() guys are a bunch of sissies.

OhFiddleDiddle + 0 comments 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.

ajk100 + 0 comments Thanks man!! Your comment got me to try that problem again.. :)

deepak_upreti + 0 comments [deleted]biswajit16 + 0 comments [deleted]shshnk28 + 0 comments this prompted me to write a proper solution!

marton_szigeti_1 + 0 comments 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..

clivic + 0 comments Why this assault gets so many upvotes?

peanutbutterr + 2 comments Having 100,000 tests in a testcase is exessive and makes debugging a pain. 1000 would have been enough to catch the badly performing implementations.

mkp07 + 1 comment I used

`git diff`

on current and expected outputs in that case.kanishk251296 + 0 comments Can u tell me how to use it

motwaniakash3295 + 10 comments For all those who are still trying to figure out why are they failing 1,2 and 3 testcase even when they are getting correct output for most, check for the following string.

---->Input: zzzayybbaa

---->correct output : zzzbaaabyy

---->incorrect output : zzzaaabbyy (what I was getting)

took me quite a while to figure it out.

adrien_boukobza + 0 comments THx a lot man!! So useful for me!!!

prcmichaelli + 0 comments So cool man!!! Just miss a "=" sign somewhere.

28599rutvik + 0 comments thanks alot...yarr this testcase is very useful..

imhktc + 0 comments Thanks!!

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

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

arpitpathak26 + 0 comments thanks a ton buddy :)

andrii_grytsenko + 1 comment thanks!

tppreetham + 0 comments [deleted]

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

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

Anmol5 + 7 comments For all those people whose code is getting failed for testcases#2 & 3, check if your code handles the condition when the length of input string is 1 i.e. single letter strings in which case the correct output would be "no answer"... that was the problem with my code. hope it helps :)

sgoel01 + 0 comments Nice :)

Helped me !

diningphil + 0 comments Thanks! :D

ksh_shrm1 + 0 comments thanks man!

vamshi09 + 1 comment 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...

Anmol5 + 1 comment It's not the single letter string test case which is failing for you. It's the other strings in the same test case. Your char arrays are all of length 100. Make them of length 101. If you get an input string of length 100, you will need an additional byte for storing '\0'.

tariqul_isha + 0 comments Thanks you!

_nothing + 0 comments That was killing me. Thanks, man/woman.

Fazith + 0 comments no use!!

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

nikhilkuria + 1 comment This was a killer for me. How much ever I tried to optimize the core algorithm, I was getting timed out in test cases 1 and 2. Finally realized the culprit was the Sysout i used in Java. Used OutputStreamWriter to solve it. phew!!

aalokahluwalia + 1 comment 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.

miracle0930 + 1 comment Could you explain how to use the OutPutStreamWriter? cause when I use this method it shows nothing on the console.

aalokahluwalia + 2 comments Writer out = new BufferedWriter(new OutputStreamWriter(System.out));

Read the javadocs on the Writer. Also when writing I had to surround the write statement with a try catch block because the method can throw an exception. Feel free to ask for more clarification.

nick64 + 0 comments Or use a StringBuffer to build the modified word, then a single System.out.println() per word

spulkit302 + 0 comments I am not able to implement writer and getting tle for test cases 1 & 2 .How can i solve my issue?

vitaminC + 8 comments My logic is: To find the next bigger string, we should start from the end of string, and find the first character that can be exchanged with something bigger on its right. Swap those chars. So, this new string has everything same with original string till the left of this exchange position. Just sort everything right of this position and we got the next possible bigger string.

`for (i = 0; i < t; i++) { string w; cin >> w; int n = w.length(); int j, k; for (j = n - 2; j >= 0; j--) { for (k = n - 1; k > j && w[k] <= w[j]; k--) ; if (k == j) continue; char tmp = w[k]; w[k] = w[j]; w[j] = tmp; sort(w.begin() + j + 1, w.end()); break; } if (j < 0) cout << "no answer" << endl; else cout << w << endl; }`

yerzhik + 0 comments 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.

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

amazinghacker + 0 comments Thanks man...wonderful logic

Tejas11 + 2 comments 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--; }`

gusval + 0 comments Uff, I'm not following your logic, but if you tried the same of yerzhik, the trick is, the "j" is the position you need the change, but is not a simple swap, first you need to Order the letters from j to Zise-1, and then swap by the firs char greather than chars[j]

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

sample: POS: 012345678 WORD:acfhomkba ind = 3 (h) then: order from 4 to 8 => [omkba]->[abkmo] => acf h abkmo then: swap chars[ind] by FIRST letter[ind to N-1] where chars[ind]>letter , => swap h by k RESULT => acfkabhmo

karthik_grandhi + 0 comments `scanf("%d",&t); for(int g=0;g<t;g++) { // char s[100],min,max,temp[100],ss[100]; char* s=(char*)malloc(sizeof(char)*100); memset(s,0,100); char* temp=(char*)malloc(sizeof(char)*100); memset(temp,0,100); char* ss=(char*)malloc(sizeof(char)*100); memset(ss,0,100); char max; scanf("%s",s); strcpy(ss,s); int len=0,cons; while(s[len]!='\0') { len++; } int c=0; for(int i=len-1;i>0;i--) { cons=i; if(s[i]<=s[i-1]) { temp[c]=s[i]; c++; } else { temp[c]=s[i]; c++; break; } } if(c==0) c++; for(int k=0;k<c;k++) { if(s[cons-1]<temp[k]) { max=s[cons-1]; s[cons-1]=temp[k]; temp[k]=max; break; } } for(int j=0;j<c;j++) { s[cons+j]=temp[j]; } if(strcmp(ss,s)) printf("%s\n",s); else printf("no answer\n"); free(s); free(ss); free(temp); } so one please help me my testcase1 and 2 showing wrong`

etayluz + 0 comments What is sort()?

sgoyal534 + 0 comments 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

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

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

avardar + 0 comments THIS NEEDS TO CHANGE

The very first test inputs need to be CONCISE which covers all the corner cases. I pass the first test case and then baaaaam, a case with 100000 inputs where I cannot easily debug and find where the difference in my output is. You are not helping anyone

Please for the love of god put smaller test cases at the beginning where it is easy to see the correctness of the algorithm. ONLY THEN put those 100000-input-cases where you need to measure performance.

itsbruce + 1 comment The Editorial solutions iterate forward from the start of the string. It makes more sense to iterate backwards from the end. In most cases, this will save a lot of time.

Since there cannot be an answer for any string smaller than two characters, take the last character of the list and place it into a separate sequence which is your sorted string. Now, working backwards along the rest of the original string...

If a character is greather than or equal to the last character in the sorted sequence, add it to the end of the sorted sequence (which keeps it sorted with no complex algorithm needed). If you reach the beginning without ever having encountered a character smaller than the last one in the sorted sequence, there can be no answer.

The first time you encounter a character which is smaller than the last (and biggest) character in the sorted sequence, you have found your solution. All you have to do now is iterate forwards through the sorted sequence until you find the first one in the sequence which is bigger. Move that to the front of the sequence and put your character in its place. Append your (nearly) sorted set to the part of the string that you haven't yet traversed. Done, with minimum traversal and no complex sorting algorithm

vabsarora90 + 0 comments I approached the problem in a similar way

bigohk + 0 comments its almost unfair for Java guys :-)

Sort 525 Discussions, By:

Please Login in order to post a comment