We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
//Simple answer with a worst cast time complexity as: O(26*n)
..Minimum lexicographically greater string can be obtained by:
Finding a position from end of string where character is lesser than a char present after that.
//Then swap that .After that from that position onwards sort the remaining string
//Use a character position vector where for all 26 characters I maintain whether an occurence is there after the index where I am.
stringbiggerIsGreater(stringw){intn=w.length();if(n==1){stringres="no answer";returnres;}//at a particular index, I am supposed to find a char that is lexicographically greater than that curr char in further indicesboolflag=false;vector<int>pos(26,-1);pos[w[n-1]-'a']=n-1;for(inti=n-2;i>=0;i--){charch=w[i];for(intj=ch-'a'+1;j<26;j++){if(pos[j]!=-1){flag=true;charch2='a'+j;w[pos[j]]=ch;w[i]=ch2;sort(w.begin()+i+1,w.end());break;}}if(flag){break;}pos[ch-'a']=i;}if(flag){returnw;}return"no answer";}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Bigger is Greater
You are viewing a single comment's thread. Return to all comments →
//Simple answer with a worst cast time complexity as: O(26*n)