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.
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
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 →
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