A person wants to go from origin to a particular location, he can move in only 4 directions(i.e East, West, North, South) but his friend gave him a long route, help a person to find minimum Moves so that he can reach to the destination.
Note: You need to print the lexicographically sorted string. Assume the string will have only ‘E’ ‘N’ ‘S’ ‘W’ characters.
Example 1:
Input:
S = "SSSNEEEW"
Output: EESS
Explanation: Following the path SSSNEEEW
and EESS gets you at the same final point.
There's no shorter path possible.
Ã¢â¬â¹Example 2:
Input: 
S = "NESNWES"
Output: E
Explanation: Following the path NESNWES
and E gets you at the same final point.
There's no shorter path possible.
Your Task:
You don't need to read input or print anything. Your task is to complete the function shortestPath() which takes the string S as input and returns the resultant string denoting the shortest path in lexicographic order.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|) for output.
Constraints:
1<=|S|<=10^{5}

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|) for output.

Starter code:
#User function Template for python3

class Solution:
    def shortestPath(self, s):
        # code here

Solutions:
class Solution:

	def shortestPath(self, s):
		ans = ''
		E = s.count('E')
		W = s.count('W')
		N = s.count('N')
		S = s.count('S')
		if E > W:
			ans += 'E' * (E - W)
		if N > S:
			ans += 'N' * (N - S)
		if S > N:
			ans += 'S' * (S - N)
		if W > E:
			ans += 'W' * (W - E)
		return ans


class Solution:

	def shortestPath(self, s):
		r = ''
		S = 0
		N = 0
		E = 0
		W = 0
		for i in s:
			if i == 'S':
				S += 1
			elif i == 'N':
				N += 1
			elif i == 'W':
				W += 1
			elif i == 'E':
				E += 1
		if E > W:
			r += 'E' * (E - W)
		if N > S:
			r += 'N' * (N - S)
		if W > E:
			r += 'W' * (W - E)
		if S > N:
			r += 'S' * (S - N)
		a = sorted(r)
		b = ''.join(a)
		return b


from collections import Counter

class Solution:

	def shortestPath(self, s):
		c = Counter(s)
		result = []
		result += ['E'] * max(0, c['E'] - c['W'])
		result += ['N'] * max(0, c['N'] - c['S'])
		result += ['S'] * max(0, c['S'] - c['N'])
		result += ['W'] * max(0, c['W'] - c['E'])
		return ''.join(result)


class Solution:

	def shortestPath(self, s):
		d = {}
		str1 = ''
		for i in s:
			if i == 'S':
				if 'N' in d.keys() and d['N'] > 0:
					d['N'] = d['N'] - 1
				else:
					d[i] = d.get(i, 0) + 1
			if i == 'N':
				if 'S' in d.keys() and d['S'] > 0:
					d['S'] = d['S'] - 1
				else:
					d[i] = d.get(i, 0) + 1
			if i == 'E':
				if 'W' in d and d['W'] > 0:
					d['W'] = d['W'] - 1
				else:
					d[i] = d.get(i, 0) + 1
			if i == 'W':
				if 'E' in d and d['E'] > 0:
					d['E'] = d['E'] - 1
				else:
					d[i] = d.get(i, 0) + 1
		for (key, value) in d.items():
			str1 += key * value
		str1 = ''.join(sorted(str1))
		return str1


class Solution:

	def shortestPath(self, s):
		(N, S, E, W) = (0, 0, 0, 0)
		st = ''
		for i in s:
			if i == 'N':
				N += 1
			elif i == 'S':
				S += 1
			elif i == 'E':
				E += 1
			else:
				W += 1
		if E > W:
			st += 'E' * (E - W)
		if N > S:
			st += 'N' * (N - S)
		if S > N:
			st += 'S' * (S - N)
		if W > E:
			st += 'W' * (W - E)
		return st


class Solution:

	def shortestPath(self, s):
		S = s.count('S')
		N = s.count('N')
		E = s.count('E')
		W = s.count('W')
		x = S - N
		y = E - W
		res = ''
		if x > 0:
			res += abs(x) * 'S'
		else:
			res += abs(x) * 'N'
		if y > 0:
			res += y * 'E'
		else:
			res += abs(y) * 'W'
		z = list(res)
		z.sort()
		st = ''
		return st.join(z)


class Solution:

	def shortestPath(self, s):
		i = j = 0
		for k in s:
			if k == 'N':
				i -= 1
			elif k == 'S':
				i += 1
			elif k == 'E':
				j += 1
			else:
				j -= 1
		res = ''
		if j > 0:
			res += 'E' * j
		if i > 0:
			res += 'S' * i
		if i < 0:
			res += 'N' * abs(i)
		if j < 0:
			res += 'W' * abs(j)
		return res


class Solution:

	def shortestPath(self, s):
		(x, y) = (0, 0)
		for i in s:
			if i == 'N':
				y += 1
			elif i == 'S':
				y -= 1
			elif i == 'E':
				x += 1
			elif i == 'W':
				x -= 1
		result = ''
		if x > 0:
			result += 'E' * x
		elif x < 0:
			result += 'W' * abs(x)
		if y > 0:
			result += 'N' * y
		elif y < 0:
			result += 'S' * abs(y)
		return ''.join(sorted(result))


class Solution:

	def shortestPath(self, S):
		n = S.count('N')
		s = S.count('S')
		w = S.count('W')
		e = S.count('E')
		ans = ''
		if e > w:
			ans += 'E' * (e - w)
		if n > s:
			ans += 'N' * (n - s)
		if s > n:
			ans += 'S' * (s - n)
		if w > e:
			ans += 'W' * (w - e)
		return ans


class Solution:

	def shortestPath(self, s):
		ans = ''
		d = {'N': 0, 'S': 0, 'E': 0, 'W': 0}
		for i in s:
			d[i] += 1
		a = d['N'] - d['S']
		if a > 0:
			ans += 'N' * a
		elif a < 0:
			ans += 'S' * abs(a)
		b = d['E'] - d['W']
		if b > 0:
			ans += 'E' * b
		elif b < 0:
			ans += 'W' * abs(b)
		return ''.join(sorted(ans))


class Solution:

	def shortestPath(self, s):
		(norSouth, eastWest) = (0, 0)
		for i in s:
			if i == 'S':
				norSouth -= 1
			elif i == 'N':
				norSouth += 1
			elif i == 'W':
				eastWest -= 1
			elif i == 'E':
				eastWest += 1
		outStr = ''
		if eastWest > 0:
			outStr += 'E' * eastWest
		if norSouth < 0:
			outStr += 'S' * abs(norSouth)
		if norSouth > 0:
			outStr += 'N' * abs(norSouth)
		if eastWest < 0:
			outStr += 'W' * abs(eastWest)
		return outStr


class Solution:

	def shortestPath(self, s):
		x = 0
		y = 0
		for i in range(len(s)):
			if s[i] == 'S':
				y -= 1
			if s[i] == 'N':
				y += 1
			if s[i] == 'W':
				x -= 1
			if s[i] == 'E':
				x += 1
		ans = ''
		while x > 0:
			ans += 'E'
			x -= 1
		while y > 0:
			ans += 'N'
			y -= 1
		while y < 0:
			ans += 'S'
			y += 1
		while x < 0:
			ans += 'W'
			x += 1
		return ans


class Solution:

	def shortestPath(self, s):
		result = ''
		if s.count('N') > s.count('S'):
			result += 'N' * abs(s.count('N') - s.count('S'))
		else:
			result += 'S' * abs(s.count('N') - s.count('S'))
		if s.count('E') > s.count('W'):
			result += 'E' * abs(s.count('E') - s.count('W'))
		else:
			result += 'W' * abs(s.count('E') - s.count('W'))
		return ''.join(sorted(result))


class Solution:

	def shortestPath(self, s):
		self.s = s
		str = ''
		x = 0
		y = 0
		for i in range(len(s)):
			if s[i] == 'W':
				x -= 1
			if s[i] == 'E':
				x += 1
			if s[i] == 'N':
				y += 1
			if s[i] == 'S':
				y -= 1
		while x != 0 or y != 0:
			if y < 0:
				str += 'S'
				y += 1
			elif y > 0:
				str += 'N'
				y -= 1
			elif x < 0:
				str += 'W'
				x += 1
			else:
				str += 'E'
				x -= 1
		str = ''.join(sorted(str))
		return str


class Solution:

	def shortestPath(self, s):
		e = 0
		st = 0
		for c in s:
			if c == 'E':
				e += 1
			elif c == 'W':
				e -= 1
			elif c == 'S':
				st += 1
			elif c == 'N':
				st -= 1
		res = ''
		if e > 0:
			res += 'E' * e
		if st < 0:
			res += 'N' * abs(st)
		if st > 0:
			res += 'S' * st
		if e < 0:
			res += 'W' * abs(e)
		return res


class Solution:

	def shortestPath(self, s):
		result = ''
		direction_count = {'N': 0, 'S': 0, 'E': 0, 'W': 0}
		meaningless = {'N': 'S', 'S': 'N', 'E': 'W', 'W': 'E'}
		for i in range(len(s)):
			direction_count[s[i]] += 1
		if direction_count['E'] > direction_count['W']:
			result += 'E' * (direction_count['E'] - direction_count['W'])
		if direction_count['N'] > direction_count['S']:
			result += 'N' * (direction_count['N'] - direction_count['S'])
		if direction_count['S'] > direction_count['N']:
			result += 'S' * (direction_count['S'] - direction_count['N'])
		if direction_count['W'] > direction_count['E']:
			result += 'W' * (direction_count['W'] - direction_count['E'])
		return result


class Solution:

	def shortestPath(self, s):
		d = {'E': 0, 'W': 0, 'N': 0, 'S': 0}
		for i in s:
			d[i] = d[i] + 1
		p = ''
		for i in s:
			if i == 'E' and d['W'] > 0:
				d['W'] -= 1
			elif i == 'E' and d['W'] == 0:
				p += 'E'
			if i == 'W' and d['E'] > 0:
				d['E'] -= 1
			elif i == 'W' and d['E'] == 0:
				p += 'W'
			if i == 'N' and d['S'] > 0:
				d['S'] -= 1
			elif i == 'N' and d['S'] == 0:
				p += 'N'
			if i == 'S' and d['N'] > 0:
				d['N'] -= 1
			elif i == 'S' and d['N'] == 0:
				p += 'S'
		return ''.join(sorted(p))


class Solution:

	def shortestPath(self, s):
		sn = s.count('S')
		nn = s.count('N')
		m = min(sn, nn)
		s = s.replace('N', '', m)
		s = s.replace('S', '', m)
		en = s.count('E')
		wn = s.count('W')
		m = min(en, wn)
		s = s.replace('W', '', m)
		s = s.replace('E', '', m)
		return ''.join(sorted(s))


class Solution:

	def shortestPath(self, s):
		m = {'N': 0, 'S': 0, 'E': 0, 'W': 0}
		for i in s:
			m[i] += 1
		t = ''
		if m['N'] > m['S']:
			t = 'N' * (m['N'] - m['S'])
		else:
			t = 'S' * (m['S'] - m['N'])
		if m['W'] > m['E']:
			t += 'W' * (m['W'] - m['E'])
		else:
			t += 'E' * (m['E'] - m['W'])
		t = sorted(t)
		return ''.join(t)


class Solution:

	def shortestPath(self, s):
		k = {}
		for x in s:
			if x in k.keys():
				k[x] += 1
			else:
				k[x] = 1
		sn = 0
		ew = 0
		if 'S' in k.keys() and 'N' in k.keys():
			sn = k['S'] - k['N']
		elif 'S' in k.keys() and 'N' not in k.keys():
			sn = k['S']
		elif 'S' not in k.keys() and 'N' in k.keys():
			sn = 0 - k['N']
		if 'E' in k.keys() and 'W' in k.keys():
			ew = k['E'] - k['W']
		elif 'E' in k.keys() and 'W' not in k.keys():
			ew = k['E']
		elif 'E' not in k.keys() and 'W' in k.keys():
			ew = 0 - k['W']
		res = ''
		if sn > 0:
			res += 'S' * sn
		else:
			res += 'N' * (sn * -1)
		if ew > 0:
			res += 'E' * ew
		else:
			res += 'W' * (ew * -1)
		ls = []
		for x in res:
			ls.append(x)
		ls.sort()
		ret = ''.join(ls)
		return ret


class Solution:

	def shortestPath(self, s):
		(N, S, E, W) = (0, 0, 0, 0)
		st = ''
		for i in s:
			if i == 'N':
				N += 1
			elif i == 'S':
				S += 1
			elif i == 'E':
				E += 1
			else:
				W += 1
		if E > W:
			st += 'E' * (E - W)
		if N > S:
			st += 'N' * (N - S)
		if S > N:
			st += 'S' * (S - N)
		if W > E:
			st += 'W' * (W - E)
		return st
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.shortestPath(s)
		print(ans)


class Solution:

	def shortestPath(self, s):
		(a, b, c, d) = ('', '', '', '')
		k = []
		e = s.count('E')
		w = s.count('W')
		n = s.count('N')
		s = s.count('S')
		if e > w:
			a = (e - w) * 'E'
		elif e == w:
			pass
		elif e < w:
			b = (w - e) * 'W'
		if n > s:
			c = (n - s) * 'N'
		elif n == s:
			pass
		elif n < s:
			d = (s - n) * 'S'
		k.append(a)
		k.append(b)
		k.append(c)
		k.append(d)
		ss = ''.join(sorted(k))
		return ss
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.shortestPath(s)
		print(ans)


class Solution:

	def shortestPath(self, s):
		ans = ''
		d = {'N': 0, 'S': 0, 'E': 0, 'W': 0}
		for i in s:
			d[i] += 1
		a = d['N'] - d['S']
		if a > 0:
			ans += 'N' * a
		elif a < 0:
			ans += 'S' * abs(a)
		b = d['E'] - d['W']
		if b > 0:
			ans += 'E' * b
		elif b < 0:
			ans += 'W' * abs(b)
		return ''.join(sorted(ans))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.shortestPath(s)
		print(ans)


class Solution:

	def shortestPath(self, s):
		N = 0
		E = 0
		W = 0
		S = 0
		ans = ''
		for ele in s:
			if ele == 'N':
				N += 1
			elif ele == 'S':
				S += 1
			elif ele == 'E':
				E += 1
			else:
				W += 1
		if E > W:
			ans += 'E' * (E - W)
		else:
			ans += 'W' * (W - E)
		if N > S:
			ans += 'N' * (N - S)
		else:
			ans += 'S' * (S - N)
		ans = list(map(str, ans))
		ans.sort()
		return ''.join(ans)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.shortestPath(s)
		print(ans)


class Solution:

	def shortestPath(self, s):
		ver = 0
		hor = 0
		ans = ''
		for ele in s:
			if ele == 'N':
				ver += 1
			elif ele == 'S':
				ver -= 1
			elif ele == 'W':
				hor += 1
			else:
				hor -= 1
		while hor < 0:
			ans += 'E'
			hor += 1
		while ver > 0:
			ans += 'N'
			ver -= 1
		while ver < 0:
			ans += 'S'
			ver += 1
		while hor > 0:
			ans += 'W'
			hor -= 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.shortestPath(s)
		print(ans)


class Solution:

	def shortestPath(self, s):
		lst = list(s)
		itr = 0
		res = [0, 0]
		while itr < len(lst):
			if lst[itr] == 'N':
				res[0] += 1
			elif lst[itr] == 'E':
				res[1] += 1
			elif lst[itr] == 'W':
				res[1] -= 1
			else:
				res[0] -= 1
			itr += 1
		result = []
		if res[0] != 0:
			if res[0] > 0:
				s1 = 'N'
			else:
				s1 = 'S'
			for itr in range(abs(res[0])):
				result.append(s1)
		if res[1] != 0:
			if res[1] > 0:
				s2 = 'E'
			else:
				s2 = 'W'
			for itr in range(abs(res[1])):
				result.append(s2)
		result.sort()
		return ''.join(result)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.shortestPath(s)
		print(ans)


class Solution:

	def shortestPath(self, s):
		ans = ''
		mp = {'S': 0, 'N': 0, 'E': 0, 'W': 0}
		for i in s:
			mp[i] += 1
		g = abs(mp['S'] - mp['N'])
		h = abs(mp['E'] - mp['W'])
		if mp['S'] > mp['N']:
			for x in range(g):
				ans += 'S'
		else:
			for x in range(g):
				ans += 'N'
		if mp['E'] > mp['W']:
			for x in range(h):
				ans += 'E'
		else:
			for x in range(h):
				ans += 'W'
		return ''.join(sorted(ans))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.shortestPath(s)
		print(ans)


class Solution:

	def shortestPath(self, s):
		N = 0
		S = 0
		E = 0
		W = 0
		result = ''
		for i in s:
			if i == 'E':
				E += 1
			elif i == 'W':
				W += 1
			elif i == 'N':
				N += 1
			elif i == 'S':
				S += 1
		if E > W:
			E = E - W
			temp = ['E'] * E
			E = 0
			W = 0
			result += ''.join(temp)
		temp = ''
		if N > S:
			N = N - S
			temp = ['N'] * N
			N = 0
			S = 0
			result += ''.join(temp)
		temp = ''
		if S > N:
			S = S - N
			temp = ['S'] * S
			N = 0
			S = 0
			result += ''.join(temp)
		temp = ''
		if W > E:
			W = W - E
			temp = ['W'] * W
			W = 0
			W = 0
			result += ''.join(temp)
		return result


class Solution:

	def shortestPath(self, s):
		s1 = sorted(s)
		(countn, counts, countw, counte) = (0, 0, 0, 0)
		for i in s:
			if i == 'N':
				countn += 1
			elif i == 'S':
				counts += 1
			elif i == 'W':
				countw += 1
			elif i == 'E':
				counte += 1
		(res1, res2) = (0, 0)
		string1 = ''
		if countn > counts:
			res1 = countn - counts
			string1 += 'N' * res1
		else:
			res1 = counts - countn
			string1 += 'S' * res1
		if counte > countw:
			res2 = counte - countw
			string1 += 'E' * res2
		else:
			res2 = countw - counte
			string1 += 'W' * res2
		string2 = sorted(string1)
		string3 = ''
		for i in string2:
			string3 += i
		return string3


class Solution:

	def shortestPath(self, s):
		x = 0
		y = 0
		S = ''
		for i in s:
			if i == 'E':
				y += 1
			elif i == 'W':
				y -= 1
			elif i == 'N':
				x -= 1
			elif i == 'S':
				x += 1
		if y > 0:
			S = S + 'E' * y
		if x < 0:
			S = S + 'N' * -x
		if x > 0:
			S = S + 'S' * x
		if y < 0:
			S = S + 'W' * -y
		return S


class Solution:

	def shortestPath(self, s):
		res = []
		(x, y) = (0, 0)
		a = {'E': [1, 0], 'W': [-1, 0], 'N': [0, 1], 'S': [0, -1]}
		for d in s:
			x += a[d][0]
			y += a[d][1]
		if x > 0:
			res += ['E' * x]
		if y > 0:
			res += ['N' * y]
		if y < 0:
			res += ['S' * abs(y)]
		if x < 0:
			res += ['W' * abs(x)]
		return ''.join(res)


class Solution:

	def shortestPath(self, s):
		s = list(s)
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		if 'N' in d.keys() and 'S' in d.keys():
			if d['N'] > d['S']:
				d['N'] = d['N'] - d['S']
				d['S'] = 0
			else:
				d['S'] = d['S'] - d['N']
				d['N'] = 0
		if 'W' in d.keys() and 'E' in d.keys():
			if d['W'] > d['E']:
				d['W'] = d['W'] - d['E']
				d['E'] = 0
			else:
				d['E'] = d['E'] - d['W']
				d['W'] = 0
		a = ''
		for i in d.keys():
			a = a + i * d[i]
		l = list(a)
		l.sort()
		return ''.join(l)


class Solution:

	def shortestPath(self, s):
		d = {}
		l = []
		for i in s:
			if i not in d.keys():
				d[i] = 1
			else:
				d[i] = d[i] + 1
		if 'S' in d.keys() and 'N' in d.keys():
			if d['S'] > d['N']:
				d['S'] = d['S'] - d['N']
				d['N'] = 0
			else:
				d['N'] = d['N'] - d['S']
				d['S'] = 0
		if 'E' in d.keys() and 'W' in d.keys():
			if d['E'] > d['W']:
				d['E'] = d['E'] - d['W']
				d['W'] = 0
			else:
				d['W'] = d['W'] - d['E']
				d['E'] = 0
		for (i, d[i]) in d.items():
			while d[i] > 0:
				l.append(i)
				d[i] = d[i] - 1
		l.sort()
		return ''.join(l)


class Solution:

	def shortestPath(self, s):
		l = []
		for ch in s:
			if ch == 'E' and 'W' in l:
				l.remove('W')
			elif ch == 'W' and 'E' in l:
				l.remove('E')
			elif ch == 'N' and 'S' in l:
				l.remove('S')
			elif ch == 'S' and 'N' in l:
				l.remove('N')
			else:
				l.append(ch)
		l.sort()
		ans = ''.join(l)
		return ans


class Solution:

	def shortestPath(self, s):
		gg = {'S': -1, 'E': 1, 'W': -1, 'N': 1}
		x = 0
		y = 0
		for i in s:
			if i == 'E' or i == 'W':
				x += gg[i]
			if i == 'N' or i == 'S':
				y += gg[i]
		ans = ''
		if x > 0:
			for i in range(x):
				ans += 'E'
		if y > 0:
			for i in range(y):
				ans += 'N'
		if y < 0:
			for i in range(abs(y)):
				ans += 'S'
		if x < 0:
			for i in range(abs(x)):
				ans += 'W'
		return ans


class Solution:

	def shortestPath(self, s):
		res = []
		n = len(s)
		for i in range(0, n):
			if s[i] == 'N' and 'S' in res:
				res.remove('S')
			elif s[i] == 'S' and 'N' in res:
				res.remove('N')
			elif s[i] == 'E' and 'W' in res:
				res.remove('W')
			elif s[i] == 'W' and 'E' in res:
				res.remove('E')
			else:
				res.append(s[i])
		o = ''
		res.sort()
		for i in res:
			o += i
		return o


class Solution:

	def shortestPath(self, s):
		st = []
		i = 0
		while i < len(s):
			if s[i] == 'S':
				if 'N' in st:
					ind = st.index('N')
					st.pop(ind)
				else:
					st.append(s[i])
			elif s[i] == 'N':
				if 'S' in st:
					ind = st.index('S')
					st.pop(ind)
				else:
					st.append(s[i])
			if s[i] == 'E':
				if 'W' in st:
					ind = st.index('W')
					st.pop(ind)
				else:
					st.append(s[i])
			if s[i] == 'W':
				if 'E' in st:
					ind = st.index('E')
					st.pop(ind)
				else:
					st.append(s[i])
			i += 1
		return ''.join(sorted(st))


class Solution:

	def shortestPath(self, s):
		l = ''
		N = E = S = W = 0
		if 'S' in s:
			S += s.count('S')
		if 'N' in s:
			N += s.count('N')
		if 'E' in s:
			E += s.count('E')
		if 'W' in s:
			W += s.count('W')
		if max(S, N) == S:
			l += (S - N) * 'S'
		if max(S, N) == N:
			l += (N - S) * 'N'
		if max(E, W) == E:
			l += (E - W) * 'E'
		if max(E, W) == W:
			l += (W - E) * 'W'
		return ''.join(sorted(l))


class Solution:

	def shortestPath(self, s):
		x = 0
		y = 0
		l = []
		for i in s:
			if i == 'S' or i == 'N':
				if i == 'S':
					y = y - 1
				else:
					y = y + 1
			if i == 'E' or i == 'W':
				if i == 'W':
					x = x - 1
				else:
					x = x + 1
		if x >= 0:
			l.append(x * 'E')
		if y >= 0:
			l.append(y * 'N')
		if y < 0:
			l.append(abs(y) * 'S')
		if x < 0:
			l.append(abs(x) * 'W')
		return ''.join(l)


class Solution:

	def shortestPath(self, s):
		a = [s.count('N'), -1 * s.count('S'), -1 * s.count('W'), s.count('E')]
		k = ''
		(b, c) = (a[0] + a[1], a[2] + a[3])
		if c > 0:
			k = k + 'E' * c
		if b > 0:
			k = k + 'N' * b
		if b < 0:
			b *= -1
			k = k + 'S' * b
		if c < 0:
			c *= -1
			k = k + 'W' * c
		return k


class Solution:

	def shortestPath(self, s):
		hm = {'E': 0, 'N': 0, 'S': 0, 'W': 0}
		for i in s:
			hm[i] += 1
		res = ''
		e = hm['E'] - hm['W']
		if e > 0:
			res += 'E' * e
		n = hm['N'] - hm['S']
		if n > 0:
			res += 'N' * n
		s = hm['S'] - hm['N']
		if s > 0:
			res += 'S' * s
		w = hm['W'] - hm['E']
		if w > 0:
			res += 'W' * w
		return res


class Solution:

	def shortestPath(self, s):
		a = s.count('S')
		b = s.count('N')
		c = s.count('E')
		d = s.count('W')
		m = ''
		if a > b:
			m = m + abs(a - b) * 'S'
		else:
			m = m + abs(a - b) * 'N'
		if c > d:
			m = m + abs(c - d) * 'E'
		else:
			m = m + abs(c - d) * 'W'
		h = sorted(m)
		return ''.join(h)


class Solution:

	def shortestPath(self, s):
		a = s.count('N')
		b = s.count('S')
		c = s.count('E')
		d = s.count('W')
		x = a - b
		y = c - d
		ans = ''
		if x > 0:
			ans += 'N' * x
		elif x < 0:
			ans += 'S' * abs(x)
		if y > 0:
			ans += 'E' * y
		elif y < 0:
			ans += 'W' * abs(y)
		return ''.join(sorted(ans))


class Solution:

	def shortestPath(self, s):
		(x, y) = (0, 0)
		(cn, cs, ce, cw) = (0, 0, 0, 0)
		s1 = ''
		for i in s:
			if i == 'N':
				if cs > 0:
					cs = cs - 1
				else:
					cn = cn + 1
			elif i == 'S':
				if cn > 0:
					cn = cn - 1
				else:
					cs = cs + 1
			elif i == 'E':
				if cw > 0:
					cw = cw - 1
				else:
					ce = ce + 1
			elif i == 'W':
				if ce > 0:
					ce = ce - 1
				else:
					cw = cw + 1
		if ce > 0:
			for i in range(ce):
				s1 = s1 + 'E'
		if cn > 0:
			for i in range(cn):
				s1 = s1 + 'N'
		if cs > 0:
			for i in range(cs):
				s1 = s1 + 'S'
		if cw > 0:
			for i in range(cw):
				s1 = s1 + 'W'
		return s1


class Solution:

	def shortestPath(self, s):
		count1 = 0
		count2 = 0
		count3 = 0
		count4 = 0
		for i in s:
			if i == 'S':
				count4 = count4 + 1
			elif i == 'N':
				count3 = count3 + 1
			elif i == 'E':
				count1 = count1 + 1
			elif i == 'W':
				count2 = count2 + 1
		count5 = count1 - count2
		count6 = count3 - count4
		s = ''
		if count5 > 0:
			s = s + 'E' * count5
		if count6 > 0:
			s = s + 'N' * count6
		if count6 <= 0:
			s = s + 'S' * -count6
		if count5 <= 0:
			s = s + 'W' * -count5
		return s


class Solution:

	def shortestPath(self, s):
		direction = 0
		out = ''
		dir_ref = {'N': 1j, 'S': -1j, 'W': -1, 'E': 1}
		for i in s:
			direction += dir_ref[i]
		for j in 'ENSW':
			(tmp_ref, tmp_direction) = (dir_ref[j].real, direction.real) if j in 'EW' else (dir_ref[j].imag, direction.imag)
			if int(tmp_ref) & 8388608 == int(tmp_direction) & 8388608:
				out += j * abs(int(tmp_direction))
		return out


class Solution:

	def shortestPath(self, s):
		temp = []
		dir_ref = {'N': 'S', 'S': 'N', 'W': 'E', 'E': 'W'}
		for i in s:
			if dir_ref[i] in temp:
				temp.remove(dir_ref[i])
			else:
				temp.append(i)
		temp = ''.join(sorted(temp))
		return ''.join(sorted(temp))


class Solution:

	def shortestPath(self, s):
		ea = s.count('E')
		no = s.count('N')
		so = s.count('S')
		we = s.count('W')
		sol = ''
		v = no - so
		h = ea - we
		if h > 0:
			sol += 'E' * abs(h)
		if v > 0:
			sol += 'N' * abs(v)
		if v < 0:
			sol += 'S' * abs(v)
		if h < 0:
			sol += 'W' * abs(h)
		return sol


class Solution:

	def shortestPath(self, s):
		N = 0
		S = 0
		E = 0
		W = 0
		for i in range(len(s)):
			if s[i] == 'N':
				N += 1
			elif s[i] == 'S':
				S += 1
			elif s[i] == 'W':
				W += 1
			else:
				E += 1
		ans = ''
		ans = ans + 'E' * (E - W)
		ans = ans + 'N' * (N - S)
		ans = ans + 'S' * (S - N)
		ans = ans + 'W' * (W - E)
		return ans


class Solution:

	def shortestPath(self, s):
		from collections import defaultdict
		path = defaultdict(int)
		pair = {'S': 'N', 'E': 'W', 'W': 'E', 'N': 'S'}
		for i in range(len(s)):
			path[s[i]] += 1
		vertical = ''
		n = path.get('N', 0)
		s = path.get('S', 0)
		if n > s:
			vertical = 'N' * (n - s)
		else:
			vertical = 'S' * (s - n)
		horizontal = ''
		e = path.get('E', 0)
		w = path.get('W', 0)
		if e > w:
			horizontal = 'E' * (e - w)
		else:
			horizontal = 'W' * (w - e)
		return ''.join(sorted(vertical + horizontal))


class Solution:

	def shortestPath(self, s):
		h = 0
		v = 0
		for i in s:
			if i == 'E':
				h += 1
			elif i == 'W':
				h -= 1
			elif i == 'N':
				v += 1
			else:
				v -= 1
		ans = ''
		if h > 0:
			ans += 'E' * h
		else:
			ans += 'W' * abs(h)
		if v > 0:
			ans += 'N' * v
		else:
			ans += 'S' * abs(v)
		return ''.join(sorted(ans))