Shortest Route Problem Statement

You want to visit your friend’s house located at some position in an infinite grid starting from origin (0, 0). You can move in four directions: East (E), West (W), North (N), and South (S).

Your friend gives you a directional string STR representing a route to their house. You need to determine the shortest possible route, minimizing the number of steps, and return the route that is also lexicographically smallest.

Input:

The first line of the input contains an integer T, the number of test cases.
Each of the next T lines contains a string STR of length N, representing the route.

Output:

For each test case, output a single line with the shortest lexicographical route string to your friend's house.

Example:

Input:
1
NNSEWEE

Output:
EEN

Explanation: For the test case where STR = "NNSEWEE", the smallest route to reach the destination (2, 1) from origin (0, 0) is 'EEN'. This route is lexicographically smallest among other options like 'NEE', 'ENE'.

Constraints:

  • 1 <= T <= 50
  • 1 <= N <= 10^4
  • STR contains only characters 'E', 'W', 'N', 'S'
  • Time limit: 1 sec.

Note:

You do not need to print anything; the function only needs to return the final result.

AnswerBot
1d

Given a directional string representing a route to a friend's house in an infinite grid, find the shortest lexicographically smallest route to reach the destination.

  • Iterate through the directional str...read more

Help your peers!
Add answer anonymously...
Buyhatke Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter