# Bigger is Greater

# Bigger is Greater

devstarj + 55 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 + 1 comment @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.

mecorre1 + 0 comments For me it threw a runtime error when I was not concidereing w.length = 1 cases.

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 + 1 comment ## 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; }`

manishmeshram51 + 0 comments this logic is to rev the string in O(n) time and O(1) space. can u explain, how this iis working?

TheLastOrca + 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!

racroi3010 + 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 + 3 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'`

lifeHasNoPurpose + 1 comment what [ : : -1] it does after range() ??

dm_dubovitsky + 1 comment it reverse the range.

lifeHasNoPurpose + 0 comments Got it, thanks.

dheerajmitra18 + 0 comments how u develop that level of thinking

santhisrigovind + 0 comments [deleted]

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 [deleted]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 -

kris_tobiasson + 0 comments Here's my JS solution. I started from the end of the string and worked backwords until I found a character that is less than something previous:

let a = `abcdefghijklmnopqrstuvwxyz`; let idVals = [[w.length-1, a.indexOf(w.charAt(w.length-1))]]; for(let i = w.length-2; i >= 0; i--){ let val = a.indexOf(w.charAt(i)); if(val < idVals[idVals.length-1][1]){ let sub = ``; for(let j = 0; j < idVals.length; j++){ let id = idVals[j][0]; if(val < idVals[j][1]){ let start = (i === 0) ? w.charAt(id) : w.substring(0,i) + w.charAt(id); sub += w.substring(i,id).split(``).sort().join(``); console.log(sub); return start + sub; } sub += w.charAt(id); } } idVals.push([i,val]); } return `no answer`;

Dhvanit_Popat + 0 comments Thanks great explanation

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 .

Sort 599 Discussions, By:

Please Login in order to post a comment