Shortest Route

Posted: 2 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You want to visit your friend’s house who lives at some location in an infinite grid. You are initially at the origin of the infinite grid and can move only in four directions (i.e East, West, North, South).

For Example, If you are at cell (X, Y) then you can move to East i.e at cell (X+1, Y), or West i.e at cell (X-1, Y), or North i.e at cell (X, Y+1), or South i.e at cell (X, Y-1).

Your friend gives you a string ‘STR’ of length ‘N’ that represents the route to his house from the origin. The string ‘STR’ has only four different characters, i.e ‘E’, ‘W’, ‘N’, ‘S’. which represent direction East, West, North, South, respectively.

You find out that the route given by your friend is very long, and a shorter route is also possible. Your task is to find the smallest route to reach your friend’s house. See the example for better clarity.

Note:

1. There can be more than one shortest route, you should return the one which is lexicographically smallest among them.

Example:

Consider that your friend’s house is in the cell (2, 1) in the grid. And the route given by your friend is represented by the string ‘STR’= “NNSEWEE”.

One of the smallest route to reach cell (2, 1) from origin i.e cell (0, 0) is given by string  “EEN”  i.e you start from the cell (0, 0), then move East, i.e at cell (1, 0), then again move East, i.e at cell (2, 0), and then finally move North i.e at cell (2, 1).

Note, there are some other smallest routes such as “NEE”,  “ENE” etc, but “EEN” is the lexicographically smallest among them, so you should return it.  
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases, then ‘T’ test cases follow.

The first line and only line of each test case consist of a string ‘STR’ of length ‘N’ representing the route given by your friend.
Output format :
For each test case, print a single line containing a lexicographically smallest string representing the smallest route to reach your friend’s house from the origin. 

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10 ^ 4
‘STR’ has only characters ‘E’, ‘W’, ‘N’ and ‘S’. 

Where ‘T’ is the total number of test cases, ‘N’ is the length of the given string ‘STR’

Time limit: 1 sec.
Approach 1

This approach is based on the fact that ‘South’ and ‘North’,  ‘East’ and ‘West’  both are opposite pairs of directions and they can cancel each other's effect.

 

We can simply iterate over the string ‘Str’ and count the number of characters ‘E’, ‘W’, ‘N’, ‘S’ present in the given string.  If the number of ‘E’s in the string ‘Str’ is ‘countE’, number of ‘W’s is ‘countW‘, number of ‘N’s is ‘countN’ and number of ‘S’s is ‘countS’,   then the length of the shortest route should be abs(countE - countW) + abs (countS-countN)

 

 

Algorithm

  • Initialize four integer variables ‘countE’:=0, ‘countW’:=0, ‘countN’:=0, ‘countS’:=0,
  • Iterate over the given string Str, and for each character in Str do the following -:
    • If the character is ‘E’, then increment ‘countE’ by 1.
    • If the character is ‘W’, then increment ‘countW’ by 1.
    • If the character is ‘S’, then increment ‘countS’ by 1.
    • If the character is ‘N’, then increment ‘countN’ by 1.
  • Create an empty string ‘result’. 
  • If ‘countE’ > ‘countW’, then append character ‘E’ (‘countE’ - ‘countW’) times in string ‘result’.
  • If ‘countN’ > ‘countS’, then append character ‘N’ (‘countN’ - ‘countS’) times in string ‘result’.
  • If ‘countS’ > ‘countN’, then append character ‘S’ (‘countS’ - ‘countN’) times in string ‘result’.
  • If ‘countW’ > ‘countE’, then append character ‘W’ (‘countW’ - ‘countE’) times in string ‘result’.
  • Return ‘result’.  
Try Problem