Shortest Route

Easy
0/40
Average time to solve is 15m
35 upvotes
Asked in companies
AmazonBuyhatkeFlipkart limited

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
S
NNSEWEE
Sample Output 1:
S
EEN
Explanation of Sample Input 1:
Test case 1:
The given string ‘STR’ has a single character ‘S’, which means, friend’s house is at cell (0, -1). There is only one shortest route to reach at cell (0, -1) from the cell (0, 0), and that route is represented by the string  ‘S’. i.e your friends already give you the shortest route.

Test case 2:
See the problem statement for an explanation.
Sample Input 2:
2
SSWWNNE
SENWWN
Sample Output 2:
W
NW
Hint

Observe that ‘South’ and ‘North’,  ‘East’ and ‘West’  both are opposite pairs of directions and they can cancel each other's effect.

Approaches (1)
Counting

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’.  
Time Complexity

O(N),  where ‘N’ is the length of a given string ‘STR’. 

 

Here, we iterate over string ‘STR’ once, which will take O(N) times, and after that in the worst case we append at most ‘N’ characters in string ‘result which will also take O(N) times. Thus, overall time complexity will be O(N) + O(N) = O(N). 

Space Complexity

O(1).

 

As we are not using any extra space therefore space complexity is constant.

Code Solution
(100% EXP penalty)
Shortest Route
Full screen
Console