New update is available. Click here to update.

Last Updated: 2 Mar, 2021

Difficulty: Easy

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

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

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

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

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

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

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.

- If the character is ‘
- 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’.**

SIMILAR PROBLEMS

Divisible Substrings

Posted: 29 Jul, 2022

Difficulty: Easy

Ninja and Numbers

Posted: 30 Jul, 2022

Difficulty: Moderate

Longest Palindromic Substring

Posted: 4 Sep, 2022

Difficulty: Moderate

Cakes

Posted: 23 Sep, 2022

Difficulty: Easy

1-3 Palindrome

Posted: 4 Oct, 2022

Difficulty: Easy

Popular Interview Problems: