Given a string S, find whether it fulfills the following criteria. 
When split from the middle, the string should give two halves having the same characters and same frequency of each character. If the number of characters in the string is odd, ignore the middle character.
Example 1:
Input: S = "abcdbca"
Output: YES
Explanation: The string has length 7 which
is odd, hence we ignore the middle character
'd'. The frequency of 'a', 'b' and 'c' is 
same in both the halves. Hence, the string
fulfills the given criteria. 
Ã¢â¬â¹Example 2:
Input: S = "abbaab"
Output: NO
Explanation: The frequency of 'a' in both
the halves is different. Hence, the string
does not fulfill the given criteria. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function passed() which takes the string S as input parameter and returns a boolean value denoting whether it fulfills the given criteria or not. 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints:
1<=|S|<=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def passed(self, s):

        # code here

Solutions:
class Solution:

	def passed(self, s):
		n = len(s)
		if n % 2 == 0:
			s1 = s[:n // 2]
			s2 = s[n // 2:]
		else:
			s1 = s[:n // 2]
			s2 = s[n // 2 + 1:]
		s1 = sorted(s1)
		s2 = sorted(s2)
		if s1 == s2:
			return True
		else:
			return False


class Solution:

	def passed(self, s):
		n = len(s)
		if n % 2 == 0:
			s1 = s[:n // 2]
			s2 = s[n // 2:]
		else:
			s1 = s[:n // 2]
			s2 = s[n // 2 + 1:]
		freq = {}
		for i in s1:
			if i not in freq:
				freq[i] = 0
			freq[i] += 1
		for i in s2:
			if i not in freq or freq[i] == 0:
				return 0
			else:
				freq[i] -= 1
		for i in freq:
			if freq[i]:
				return 0
		return 1


class Solution:

	def passed(self, s):
		l = len(s)
		if l % 2 == 0:
			s1 = s[0:l // 2]
			s2 = s[l // 2:l]
		else:
			s1 = s[0:l // 2]
			s2 = s[l // 2 + 1:l]
		if sorted(s1) == sorted(s2):
			return 1
		else:
			return 0


from collections import Counter

class Solution:

	def passed(self, s):
		n = len(s)
		m = n // 2
		if n % 2 == 0:
			a = s[:m]
			b = s[m:]
		else:
			a = s[:m]
			b = s[m + 1:]
		a1 = sorted(a)
		b1 = sorted(b)
		if a1 == b1:
			return True
		return False


class Solution:

	def passed(self, s):
		k = len(s)
		if k % 2 == 0:
			mid = k // 2
			right = s[mid:]
			left = s[:mid]
			right = sorted(right)
			left = sorted(left)
			if left == right:
				return True
			else:
				return False
		else:
			mid = k // 2 + 1
			right = s[mid:]
			left = s[:mid - 1]
			right = sorted(right)
			left = sorted(left)
			if right == left:
				return True
			else:
				return False


class Solution:

	def passed(self, s):
		length = len(s)
		if length % 2 == 0:
			fp = list(s[:length // 2])
			lp = list(s[length // 2:])
			fp.sort()
			lp.sort()
			if fp == lp:
				return True
			else:
				return False
		else:
			fp = list(s[:length // 2])
			lp = list(s[length // 2 + 1:])
			fp.sort()
			lp.sort()
			if fp == lp:
				return True
			else:
				return False


import collections

class Solution:

	def passed(self, s):
		d = len(s)
		k = []
		l = []
		if d % 2 == 0:
			k = s[0:d // 2]
			l = s[d // 2:]
		else:
			x = d // 2
			k = s[0:x]
			l = s[x + 1:]
		s1 = sorted(k)
		s2 = sorted(l)
		if s1 == s2:
			return 1
		return 0


class Solution:

	def passed(self, S):
		n = len(S)
		if n % 2 == 0:
			fh = S[0:n // 2]
			sh = S[n // 2:n]
		else:
			N = (n - 1) // 2
			fh = S[0:N]
			sh = S[N + 1:n]
		f = list(fh)
		s = list(sh)
		f = sorted(f)
		s = sorted(s)
		if f == s:
			return True
		else:
			return False


class Solution:

	def passed(self, s):
		s_left = list(s[:len(s) // 2])
		s_left.sort()
		s_right = list(s[-(len(s) // 2):])
		s_right.sort()
		return s_left == s_right


class Solution:

	def passed(self, s):
		n = len(s) // 2
		return sorted([*s[:n]]) == sorted([*s[-n:]])


class Solution:

	def passed(self, s):
		a = s[:len(s) // 2]
		b = s[len(s) // 2 + 1:]
		if len(s) % 2 == 0:
			b = s[len(s) // 2] + b
		a = sorted(a)
		b = sorted(b)
		if a == b:
			return True
		else:
			return False


class Solution:

	def passed(self, s):
		if len(s) % 2 == 0:
			k = len(s) // 2
			a = s[:k]
			b = s[k:]
		else:
			k = len(s) // 2
			a = s[:k]
			b = s[k + 1:]
		d = dict()
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		m = dict()
		for i in b:
			if i not in m:
				m[i] = 1
			else:
				m[i] += 1
		import operator
		w = sorted(d.items(), key=operator.itemgetter(0))
		g = sorted(m.items(), key=operator.itemgetter(0))
		if w == g:
			return 1
		return 0


from collections import Counter

class Solution:

	def passed(self, s):
		n = len(s)
		mid = n // 2
		if n % 2 == 1:
			a = s[:mid]
			b = s[mid + 1:]
			a = sorted(a)
			b = sorted(b)
			if a == b:
				return True
			else:
				return False
		else:
			a = s[:mid]
			b = s[mid:]
			a = sorted(a)
			b = sorted(b)
			if a == b:
				return True
			else:
				return False


class Solution:

	def passed(self, s):
		_len = int(len(s) / 2)
		l = ''.join(sorted(s[:_len]))
		r = ''.join(sorted(s[_len:])) if len(s) % 2 == 0 else ''.join(sorted(s[_len + 1:]))
		if l == r:
			return True
		else:
			return False


class Solution:

	def passed(self, s):
		l1 = ''
		l2 = ''
		if len(s) % 2 == 0:
			l1 = s[:len(s) // 2]
			l2 = s[len(s) // 2:]
		else:
			l1 = s[:len(s) // 2]
			l2 = s[len(s) // 2 + 1:]
		d1 = {k1: 0 for k1 in set(l1)}
		d2 = {k1: 0 for k1 in set(l2)}
		for i1 in l1:
			d1[i1] += 1
		for j1 in l2:
			d2[j1] += 1
		if d1 == d2:
			return True
		else:
			return False


class Solution:

	def passed(self, s):
		s1 = s[:len(s) // 2]
		s2 = s[len(s) // 2 + 1:len(s)] if len(s) % 2 == 1 else s[len(s) // 2:len(s)]
		a = []
		b = []
		for i in range(len(s) // 2):
			a.append(s1[i])
			b.append(s2[i])
		a.sort()
		b.sort()
		if a == b:
			return True
		else:
			return False


class Solution:

	def passed(self, s):
		MAX_CHAR = 26
		count1 = [0] * MAX_CHAR
		count2 = [0] * MAX_CHAR
		n = len(s)
		if n == 1:
			return true
		i = 0
		j = n - 1
		while i < j:
			count1[ord(s[i]) - ord('a')] += 1
			count2[ord(s[j]) - ord('a')] += 1
			i += 1
			j -= 1
		for i in range(MAX_CHAR):
			if count1[i] != count2[i]:
				return False
		return True


class Solution:

	def passed(self, s):
		n = len(s)
		l = []
		r = []
		cl = {}
		cr = {}
		x = n >> 1
		if n & 1 == 0:
			for i in range(x):
				l.append(s[i])
			for i in range(x, n):
				r.append(s[i])
		else:
			for i in range(x):
				l.append(s[i])
			for i in range(x + 1, n):
				r.append(s[i])
		for element in l:
			if element in cl:
				cl[element] += 1
			else:
				cl[element] = 1
		for element in r:
			if element in cr:
				cr[element] += 1
			else:
				cr[element] = 1
		if cl == cr:
			return True
		return False


class Solution:

	def passed(self, s):
		return sorted(s[:int(len(s) / 2)]) == sorted(s[int(len(s) / 2):]) if len(s) % 2 == 0 else sorted(s[:int(len(s) / 2)]) == sorted(s[int(len(s) / 2) + 1:])


class Solution:

	def passed(self, s):
		l = len(s)
		if l % 2 != 0:
			s1 = s[:l // 2]
			s2 = s[l // 2 + 1:]
			dis1 = {}
			for x in s1:
				if x in dis1:
					dis1[x] += 1
				else:
					dis1[x] = 1
			dis2 = {}
			for x in s2:
				if x in dis2:
					dis2[x] += 1
				else:
					dis2[x] = 1
			try:
				for x in s2:
					if dis2[x] != dis1[x]:
						return False
				return True
			except:
				return False
		else:
			s1 = s[:l // 2]
			s2 = s[l // 2:]
			dis1 = {}
			for x in s1:
				if x in dis1:
					dis1[x] += 1
				else:
					dis1[x] = 1
			dis2 = {}
			for x in s2:
				if x in dis2:
					dis2[x] += 1
				else:
					dis2[x] = 1
			try:
				for x in s2:
					if dis2[x] != dis1[x]:
						return False
				return True
			except:
				return False


class Solution:

	def passed(self, s):
		d = {}
		n = len(s)
		a = s[:n // 2]
		b = s[n // 2 + 1:]
		if n % 2 == 0:
			b = s[n // 2:]
		for i in a:
			d[i] = d.get(i, 0) + 1
		for i in b:
			d[i] = d.get(i, 0) - 1
		for v in d.values():
			if v != 0:
				return False
		return True


class Solution:

	def passed(self, s):
		n = len(s)
		if n % 2 == 0:
			mid = n // 2
			right = s[mid:]
			left = s[:mid]
			if sorted(right) == sorted(left):
				return True
			else:
				return False
		else:
			mid = n // 2 + 1
			right = s[mid:]
			left = s[:mid - 1]
			if sorted(right) == sorted(left):
				return True
			else:
				return False
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.passed(s)
		if ans:
			print('YES')
		else:
			print('NO')


class Solution:

	def passed(self, s):
		n = len(s)
		j = n // 2
		freq_h1 = [0] * 26
		freq_h2 = [0] * 26
		if n % 2 != 0:
			h1 = s[:j]
			h2 = s[j + 1:]
		else:
			h1 = s[:j]
			h2 = s[j:]
		for ele in h1:
			pos = ord(ele) - ord('a')
			freq_h1[pos] += 1
		for ele in h2:
			pos = ord(ele) - ord('a')
			freq_h2[pos] += 1
		for i in range(26):
			if freq_h1[i] != freq_h2[i]:
				return 0
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.passed(s)
		if ans:
			print('YES')
		else:
			print('NO')


class Solution:

	def passed(self, s):
		if len(s) % 2 == 0:
			s1 = s[:len(s) // 2]
			s2 = s[len(s) // 2:]
		else:
			s1 = s[:len(s) // 2]
			s2 = s[len(s) // 2 + 1:]
		ss1 = ''.join(sorted(s1))
		ss2 = ''.join(sorted(s2))
		for i in range(len(s) // 2):
			if ss1[i] != ss2[i]:
				return False
		return True
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.passed(s)
		if ans:
			print('YES')
		else:
			print('NO')


class Solution:

	def passed(self, s):
		mid = len(s) // 2
		if len(s) % 2 == 0:
			x = s[mid:]
		else:
			x = s[mid + 1:]
		y = set(x[:mid])
		z = s[0:mid]
		for i in y:
			if z.count(i) != x.count(i):
				return False
			elif i not in x:
				return False
		return True
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.passed(s)
		if ans:
			print('YES')
		else:
			print('NO')


class Solution:

	def passed(self, s):
		lst1 = list(s)
		d1 = {}
		d2 = {}
		for itr in range(len(lst1) // 2):
			if lst1[itr] in d1.keys():
				d1[lst1[itr]] += 1
			else:
				d1[lst1[itr]] = 1
		if len(lst1) % 2 == 0:
			k = len(lst1) // 2
		else:
			k = len(lst1) // 2 + 1
		for itr in range(k, len(lst1)):
			if lst1[itr] in d2.keys():
				d2[lst1[itr]] += 1
			else:
				d2[lst1[itr]] = 1
		if d1 == d2:
			return True
		else:
			return False
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.passed(s)
		if ans:
			print('YES')
		else:
			print('NO')


class Solution:

	def passed(self, s):
		n = len(s)
		d = n // 2
		if n % 2 == 0:
			e = d
		else:
			e = d + 1
		m = s[:d]
		n = s[e:]
		m = sorted(m)
		m = ''.join(m)
		n = sorted(n)
		n = ''.join(n)
		return m == n
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.passed(s)
		if ans:
			print('YES')
		else:
			print('NO')


class Solution:

	def passed(self, s):
		maparr = [0] * 26
		i = 0
		j = len(s) - 1
		while i < j:
			x = ord(s[i]) - 97
			y = ord(s[j]) - 97
			maparr[x] += 1
			maparr[y] -= 1
			i += 1
			j -= 1
		for n in range(26):
			if maparr[n] > 0:
				return False
		return True
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		ans = ob.passed(s)
		if ans:
			print('YES')
		else:
			print('NO')


class Solution:

	def passed(self, s):
		l = int(len(s))
		if l % 2 == 0:
			s1 = s[0:l // 2]
			s2 = s[l // 2:]
			res1 = ''.join(sorted(s1))
			res2 = ''.join(sorted(s2))
			if res1 == res2:
				return True
			else:
				return False
		else:
			s3 = s[0:l // 2]
			s4 = s[l // 2 + 1:]
			res3 = ''.join(sorted(s3))
			res4 = ''.join(sorted(s4))
			if res3 == res4:
				return True
			else:
				return False


class Solution:

	def passed(self, s):
		l = []
		l1 = []
		if len(s) % 2 == 0:
			l = [s[i] for i in range(len(s) // 2)]
			l1 = [s[i] for i in range(len(s) // 2, len(s))]
		else:
			l = [s[i] for i in range(len(s) // 2)]
			l1 = [s[i] for i in range(len(s) // 2 + 1, len(s))]
		l.sort()
		l1.sort()
		if l == l1:
			return 1
		return 0


class Solution:

	def passed(self, s):
		n = len(s)
		if n % 2 == 0:
			fh = s[0:n // 2]
			sh = s[n // 2:]
			l1 = sorted(fh)
			l2 = sorted(sh)
			if l1 == l2:
				return True
			else:
				return False
		else:
			fh = s[0:n // 2]
			sh = s[n // 2 + 1:]
			l1 = sorted(fh)
			l2 = sorted(sh)
			if l1 == l2:
				return True
			else:
				return False


from collections import Counter

class Solution:

	def passed(self, s):
		n = len(s)
		x = n // 2
		if n % 2 == 0:
			a = s[:x]
			b = s[x:]
			c = Counter(a)
			d = Counter(b)
		else:
			a = s[:x]
			b = s[x + 1:]
			c = Counter(a)
			d = Counter(b)
		for i in c:
			if c[i] != d[i]:
				return 0
		return 1


class Solution:

	def passed(self, s):
		first = [0] * 26
		second = [0] * 26
		s = s.lower()
		a = len(s)
		for i in range(a // 2):
			first[ord(s[i]) - ord('a')] += 1
		if len(s) % 2 == 0:
			for i in range(a // 2, a):
				second[ord(s[i]) - ord('a')] += 1
		else:
			for i in range(a // 2 + 1, a):
				second[ord(s[i]) - ord('a')] += 1
		for i in range(len(first)):
			if first[i] != second[i]:
				return False
		return True


class Solution:

	def passed(self, s):
		d1 = {}
		for i in range(len(s) // 2):
			if s[i] in d1:
				d1[s[i]] += 1
			else:
				d1[s[i]] = 1
		d2 = {}
		if len(s) % 2 == 0:
			m = 0
		else:
			m = 1
		for i in range(len(s) // 2 + m, len(s)):
			if s[i] not in d1:
				return False
			elif d1[s[i]] == 0:
				return False
			d1[s[i]] -= 1
		for i in d1:
			if d1[i] != 0:
				return False
		return True


class Solution:

	def passed(self, s):
		l = list(s)
		le = len(s)
		if le % 2 != 0:
			m = int(le / 2)
			fh = l[:m]
			sh = l[m + 1:]
			for i in fh:
				if len(fh) == len(sh):
					if fh.count(i) == sh.count(i):
						continue
					else:
						return False
			return True
		else:
			m = int(le / 2)
			fh = l[:m]
			sh = l[m:]
			for i in fh:
				if fh.count(i) == sh.count(i):
					continue
				else:
					return False
			return True