Explanation : If you look in terms on just numbers lets say 2314 (bcad thinking in terms of alphabets or ascii can be tricky) the immideate next of this is 2341 bcda so we traverse from the last till we find an element which is greater than the previous element 23[1]4 here its one then we have to swap with the element next to it if we swap these elements we somewhat have the solution but
if its 1432 the immideate next is 2134 which we get by, first as explained above selecting the element which have the next element greater than it [1]432 and after we do swapping. so we will get the result as 4132 but its not correct right because to find the immideate next we need to swap the selected element with the closest element from the rest of the array hence a second for loop. to the the elemenets that needs to be sorted will become [1] 4 3 [2] for the selected element 1 the immideate next in the remaning array is 2. so we will get the output 2431 but one last hurdle is after swapping the elements after the swapped element need to be sorted 2[431] 431 as thats how we will get the nearest next so i will become 2134
I would be happy if you upvoted my effort explaning
def biggerIsGreater(w): w_list = list(w) swap_by = "" swap_loc = 0 if(w.count(w[0])==len(w_list)): return "no answer" for i in range(len(w_list)-1,0,-1): if(w_list[i-1] < w_list[i]): swap_pos = i-1 swap_ele = w_list[i-1] #pick should be nearest greater than distance = ord(min(w))+ord(max(w)) for j in range(swap_pos+1, len(w_list)): if(w_list[j]>swap_ele): #we need to find the nearest next if( distance > ord(w_list[j])-ord(swap_ele)): distance = ord(w_list[j])-ord(swap_ele) swap_by = w_list[j] swap_loc = j #after the completion of this loop we will have the nearest #next element temp = w_list[swap_loc] w_list[swap_loc] = w_list[swap_pos] w_list[swap_pos] = temp # from swap_pos+1 till len(w_list) sort and replace the orginal list second_half = sorted(w_list[swap_pos+1:len(w_list)]) first_half = ''.join(w_list[:swap_pos+1]) first_half+=''.join(second_half) return(first_half) #print( string[swap_pos+1:len(w_list)].sort() ) elif(i-1 == 0): return "no answer"
for _ in range(int(input())): s = input() s = list(s[::-1]) done = 0 for i in range(1,len(s)): if s[i-1] > s[i]: for j in range(i): if s[j] > s[i]: s[j],s[i] = s[i],s[j] s = sorted(s[:i])[::-1] + s[i:] print("".join(s[::-1])) break break else: print("no answer")
Here a good comment: https://www.hackerrank.com/challenges/bigger-is-greater/forum/comments/52690 But I wrote my text before I read the solution.
You have to think about the situation like about different Numeral_system. For example word: "cxrzy". "c"=1, "r"= 2, "x"=3, "y" =4, "z" =5 So we have number "13254".
So the nubmer we need: "13425" => "cxyrz"- Find symbol/position where number is lower than previous when you go from end to begin. It will target1.
- Find symbol wich is more than target1 by value, but the closest one. It will be target2.
- Swap values target1 and target2.
- Sort part from target1 to end.
string biggerIsGreater(string w) { int target = -1; int target2 = -1; for(int i=w.size()-1;i>=0;i--){ if(w[i]-'a'>w[i-1]-'a'){ target = i-1; break; } } if(target==-1){ return "no answer"; } for(int i=w.size()-1;i>=0;i--){ if(w[i]-'a'>w[target]-'a'){ target2=i; break; } } swap(w[target],w[target2]); reverse(w.begin()+target+1,w.end()); return w; }
def biggerIsGreater(w): alphabets = list(w) alphabets_copy = alphabets.copy() for i in range(-2,-len(alphabets)-1, -1): if alphabets[i] < alphabets[i+1]: for j in range(-1,i,-1): if alphabets[i] < alphabets[j]: alphabets[i], alphabets[j] = alphabets[j], alphabets[i] break alphabets[i+1:] = sorted(alphabets[i+1:]) break if alphabets_copy == alphabets: return "no answer" else: return ''.join(alphabets)
Sort 868 Discussions, By:
Please Login in order to post a comment