Billy is going to his grandmother's house. To help him do that, his mother has written down a detailed list of instructions for him to follow. Each instruction is a character 'N', 'S', 'W' or 'E', telling him to go exactly 1 block to the north, south, west or east, respectively. Billy's city consists of an infinitely large grid of streets, where each street extends infinitely to both sides, and the space between 2 adjacent streets going in the same direction is always 1 block. Billy's house and his grandmother's house are both located at street corners in this city.
Billy knows that his mother does not always choose the shortest path. Therefore, he wants to make a new list of instructions that will also lead him to his grandmother's house, but uses the minimum possible number of instructions.
You will be given inst, a String with the original list made by Billy's mom. Return the new list Billy wants. If
there are several solutions, return the one that comes first alphabetically.
|