Given a string S, Check if characters of the given string can be rearranged to form a palindrome.
Note: You have to return 1 if it is possible to convert the given string into palindrome else return 0. 
Example 1:
Input:
S = "geeksogeeks"
Output: Yes
Explanation: The string can be converted
into a palindrome: geeksoskeeg
Example 2:
Input: 
S = "geeksforgeeks"
Output: No
Explanation: The given string can't be
converted into a palindrome.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isPossible() which takes the string S as input and returns 1 if the string can be converted into a palindrome. Else, it returns 0.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(Distinct Characters).
Constraints:
1 <= |S| <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:



    def isPossible(self, S):



        # code here

Solutions:
class Solution:

	def isPossible(self, S):
		m = {}
		for i in S:
			if i in m.keys():
				m[i] += 1
			else:
				m[i] = 1
		odd = 0
		for key in m:
			if m[key] % 2 == 1:
				odd += 1
		if odd > 1:
			return 0
		return 1


class Solution:

	def isPossible(self, S):
		d = [0] * (ord('z') - ord('a') + 1)
		for i in S:
			d[ord(i) - ord('a')] += 1
		odd = 0
		for i in d:
			if i % 2 != 0:
				odd += 1
			if odd > 1:
				return False
		return True


class Solution:

	def isPossible(self, S):
		count = [0] * 26
		for c in S:
			count[ord(c) - ord('a')] += 1
		odd_count = 0
		for c in count:
			if c % 2 == 1:
				odd_count += 1
			if odd_count > 1:
				return 0
		return 1


class Solution:

	def isPossible(self, S):
		d = {x: 0 for x in S}
		s = set(S)
		e = 0
		o = 0
		for i in S:
			d[i] += 1
		for i in d:
			if d[i] % 2 != 0:
				o += 1
			else:
				e += 1
		z = len(s)
		if e == z - 1 and o == 1:
			return 1
		elif e == z:
			return 1
		return 0


class Solution:

	def isPossible(self, S):
		char_dict = {}
		count = 0
		for index in range(len(S)):
			if char_dict.get(S[index]) is not None:
				char_dict[S[index]] += 1
			else:
				char_dict[S[index]] = 1
		for (key, values) in char_dict.items():
			if values % 2 != 0:
				count += 1
		if count == 0 or count == 1:
			return True
		return False


class Solution:

	def isPossible(self, s):
		isOdd = False if len(s) % 2 == 0 else True
		oddCount = 0
		d = {}
		for c in s:
			d[c] = d.get(c, 0) + 1
		for c in d.keys():
			if not isOdd and d[c] % 2 != 0:
				return 0
			elif oddCount > 1 and isOdd:
				return 0
			elif d[c] % 2 != 0:
				oddCount += 1
		if isOdd and oddCount > 1:
			return 0
		return 1


from collections import Counter

class Solution:

	def isPossible(self, s):
		d = Counter(s)
		odd = 0
		for i in d:
			if int(d[i]) % 2 == 1:
				odd += 1
		if odd > 1:
			return 0
		else:
			return 1


class Solution:

	def isPossible(self, S):
		nonpair = 0
		n = len(S)
		d = {}
		for i in S:
			d[i] = d.get(i, 0) + 1
		for j in d.values():
			if j % 2 != 0:
				nonpair += 1
		if n % 2 == 0:
			if nonpair > 0:
				return 0
			return 1
		else:
			if nonpair > 1:
				return 0
			return 1


class Solution:

	def isPossible(self, S):
		map = {}
		for i in range(len(S)):
			if S[i] in map:
				map[S[i]] += 1
			else:
				map[S[i]] = 1
		n = len(S)
		count = 0
		for (x, y) in map.items():
			if n % 2 == 0:
				if y % 2 != 0:
					return 0
			else:
				if count > 1:
					return 0
				if y % 2 != 0:
					count += 1
		return 1


class Solution:

	def isPossible(self, S):
		k = [x for x in S]
		k = list(set(k))
		if len(S) % 2 == 1:
			c = 0
			for i in range(len(k)):
				if S.count(k[i]) % 2 == 1:
					c = c + 1
			if c > 1:
				return 0
			else:
				return 'Yes'
		if len(S) % 2 == 0:
			c = 0
			for i in range(len(k)):
				if S.count(S[i]) % 2 == 1:
					c = c + 1
			if c > 0:
				return 0
			else:
				return 'Yes'


class Solution:

	def isPossible(self, S):
		odd_chars = set()
		for c in S:
			if c in odd_chars:
				odd_chars.remove(c)
			else:
				odd_chars.add(c)
		return len(odd_chars) <= 1


from collections import Counter

class Solution:

	def isPossible(self, A):
		count = {}
		for i in S:
			count[i] = count.get(i, 0) + 1
		odd = 0
		for i in count.values():
			if i % 2 == 1:
				odd += 1
				if odd > 1:
					return 0
		return 1


class Solution:

	def isPossible(self, s):
		c = {}
		for char in s:
			c[char] = c.get(char, 0) + 1
		odd_count = 0
		for count in c.values():
			if count % 2 != 0:
				odd_count += 1
		if odd_count > 1:
			return 0
		else:
			return 1


class Solution:

	def isPossible(self, s):
		d = {}
		c = 0
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d:
			if d[i] % 2 != 0:
				c += 1
		if c > 1:
			return 0
		else:
			return 1


from collections import Counter

class Solution:

	def isPossible(self, S):
		len_ = len(S)
		half = len_ // 2
		if len_ % 2 != 0:
			first_Half = S[0:half]
			middle = S[half]
			second_Half = S[half + 1:]
		else:
			first_Half = S[0:half]
			middle = ''
			second_Half = S[half:]
		dict_1 = dict(Counter(first_Half))
		dict_2 = dict(Counter(second_Half))
		if dict_1 == dict_2:
			return 1
		else:
			return 0


from collections import defaultdict

class Solution:

	def isPossible(self, S):
		d = defaultdict(lambda : 0)
		oddCount = 0
		for i in S:
			d[i] += 1
		for values in d.values():
			if values % 2 == 0:
				continue
			else:
				oddCount += 1
		if len(S) % 2 == 0 and oddCount == 0:
			return True
		elif len(S) % 2 != 0 and oddCount == 1:
			return True
		else:
			return False


class Solution:

	def isPossible(self, S):
		count = {}
		for i in S:
			count[i] = count.get(i, 0) + 1
		odd = 0
		for i in count.values():
			if i % 2 == 1:
				odd += 1
				if odd > 1:
					return 0
		return 1


class Solution:

	def isPossible(self, S):
		dic = dict()
		for it in S:
			if it not in dic:
				dic[it] = 1
			else:
				dic[it] += 1
		flag = False
		for it in dic:
			if dic[it] % 2 == 1:
				if flag == True:
					return False
				flag = True
		return True


from collections import Counter

class Solution:

	def isPossible(self, S):
		return sum([value % 2 for value in Counter(S).values()]) == len(S) % 2


class Solution:

	def isPossible(self, a):
		a_freq = {}
		for i in a:
			if i in a_freq.keys():
				a_freq[i] = a_freq[i] + 1
			else:
				a_freq[i] = 1
		odd = 0
		for k in a_freq.keys():
			if a_freq[k] % 2 != 0:
				odd = odd + 1
		if odd > 1:
			return 0
		return 1


from collections import Counter

class Solution:

	def isPossible(self, S):
		if S == S[::-1]:
			return True
		count = 0
		for val in Counter(S).values():
			if val % 2 != 0:
				count += 1
		return True if count == 1 or count == 0 else False


from collections import Counter

class Solution:

	def isPossible(self, S):
		A = Counter(S)
		count = 0
		for i in A.keys():
			if A[i] % 2 != 0:
				count += 1
				if count > 1:
					return 0
		return 1


class Solution:

	def isPossible(self, S):
		d = {}
		for i in S:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		flag = 0
		for i in d.values():
			if i % 2 == 1:
				flag += 1
		if flag <= 1:
			return 1
		return 0


from collections import Counter

class Solution:

	def isPossible(self, S):
		ap = {}
		for i in range(len(S)):
			ap[S[i]] = 1 + ap.get(S[i], 0)
		return sum([i % 2 for i in ap.values()]) == len(S) % 2


class Solution:

	def isPossible(self, S):
		l1 = set(S)
		l2 = []
		for i in l1:
			l2.append(S.count(i))
		even = 0
		odd = 0
		for i in l2:
			if i % 2 == 0:
				even += 1
			if i % 2 != 0:
				odd += 1
		if even >= 1 and (odd == 0 or odd == 1):
			return 1
		else:
			return 0


class Solution:

	def isPossible(self, S):
		a = []
		d = {}
		for i in S:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d:
			a.append(d[i])
		count = 0
		for i in a:
			if i % 2 == 1:
				count = count + 1
		if count > 1:
			return False
		else:
			return True


class Solution:

	def isPossible(self, S):
		a = [0] * 26
		for i in S:
			a[ord(i) - 97] = a[ord(i) - 97] + 1
		c = 0
		for i in a:
			if i % 2 == 1:
				c += 1
		if c == 1 or c == 0:
			return 1
		return 0


class Solution:

	def isPossible(self, S):
		symetry = len(S) // 2
		str1 = S[:symetry]
		if len(S) % 2 == 0:
			str2 = S[symetry:]
		else:
			str2 = S[symetry + 1:]
		if str1 == str2:
			return 1
		return 0


class Solution:

	def isPossible(self, S):
		freq = {}
		for c in S:
			if c in freq:
				freq[c] += 1
			else:
				freq[c] = 1
		check = 0
		for i in freq.values():
			if i % 2 == 1:
				check += 1
		if check <= 1:
			return 1
		return 0


class Solution:

	def isPossible(self, S):
		f = {}
		for i in S:
			if i in f:
				f[i] += 1
			else:
				f[i] = 1
		odd = 0
		for i in f.values():
			if i % 2 != 0:
				odd += 1
		if len(S) % 2 == 0:
			if odd == 0:
				return True
			else:
				return False
		elif odd == 1:
			return True
		else:
			return False


class Solution:

	def isPossible(self, S):
		temp = []
		new1 = set(S)
		for i in new1:
			count = S.count(i)
			temp.append(count)
		if len(S) % 2 == 0:
			for i in temp:
				if i % 2 != 0:
					return 0
			return 1
		else:
			count1 = 0
			for i in temp:
				if i % 2 != 0:
					count1 += 1
			if count1 > 1:
				return 0
			else:
				return 1


from collections import Counter

class Solution:

	def isPossible(self, S):
		c = Counter(S)
		temp = 0
		for i in c.values():
			if i % 2 != 0:
				temp += 1
			if temp > 1:
				return 0
		return 1


class Solution:

	def isPossible(self, strr):
		listt = []
		for i in range(len(strr)):
			if strr[i] in listt:
				listt.remove(strr[i])
			else:
				listt.append(strr[i])
		if len(strr) % 2 == 0 and len(listt) == 0 or (len(strr) % 2 == 1 and len(listt) == 1):
			return True
		else:
			return False


class Solution:

	def isPossible(self, S):
		freq = {}
		for x in S:
			if x in freq:
				freq[x] += 1
			else:
				freq[x] = 1
		odd = 0
		for x in freq.values():
			if x % 2 == 1:
				odd += 1
		if len(S) % 2 == 0:
			if odd == 0:
				return True
			else:
				return False
		elif odd == 1:
			return True
		else:
			return False


class Solution:

	def isPossible(self, S):
		l = len(S)
		even = 0
		odd = 0
		if l % 2 == 0:
			a = 0
			for i in list(set(list(S))):
				a = S.count(i)
				if a % 2 == 0:
					even = even + 1
				elif a % 2 == 1:
					odd = odd + 1
			if odd == 0:
				return 1
			else:
				return 0
		elif l % 2 == 1:
			a = 0
			for j in list(set(list(S))):
				a = S.count(j)
				if a % 2 == 0:
					even = even + 1
				elif a % 2 == 1:
					odd = odd + 1
			if odd == 1:
				return 1
			else:
				return 0


class Solution:

	def isPossible(self, S):
		dict = {}
		for i in S:
			if dict.get(i) == None:
				dict.update({i: 1})
			else:
				dict.update({i: dict.get(i) + 1})
		isOnlyOdd = False
		for i in dict:
			if dict[i] % 2 != 0:
				if isOnlyOdd == True:
					return False
				else:
					isOnlyOdd = True
		return True


class Solution:

	def isPossible(self, S):
		from collections import Counter
		S = Counter(S)
		count = 0
		for i in S:
			if S[i] % 2 != 0:
				count = count + 1
		if count == 0 or count == 1:
			return 1
		else:
			return 0


class Solution:

	def isPossible(self, S):
		occurance = {}
		odd = 0
		for char in S:
			occurance[char] = occurance.get(char, 0) + 1
		for value in occurance.values():
			if value % 2 != 0:
				odd += 1
		if odd > 1:
			return 0
		return 1


from collections import Counter

class Solution:

	def isPossible(self, S):
		lis = Counter(S)
		count = 0
		for (j, k) in lis.items():
			if k % 2 != 0:
				count += 1
		if count > 1:
			return 0
		return 1


class Solution:

	def isPossible(self, S):
		d = {}
		for i in S:
			d[i] = 0
		for i in S:
			d[i] += 1
		count = 0
		for i in d:
			if d[i] % 2 == 1:
				count += 1
		if count > 1:
			return False
		return True


class Solution:

	def isPossible(self, S):
		if S == S[::-1]:
			return True
		else:
			l = ''
			for i in range(len(S)):
				if i != len(S) // 2:
					l += S[i]
			d = {}
			for i in l:
				if i not in d:
					d[i] = 1
				else:
					d[i] += 1
			c = 0
			for i in d:
				if d[i] % 2 == 1:
					if i != S[len(S) // 2]:
						c += 1
		if c != 0:
			return False
		else:
			return True


class Solution:

	def isPossible(self, S):
		S = list(S)
		l = len(S) // 2
		a = sorted(S[0:l])
		if len(S) % 2 != 0:
			b = sorted(S[l + 1:l * 2 + 1])
		else:
			b = sorted(S[l:l * 2 + 1])
		if a != b:
			return False
		return True


class Solution:

	def isPossible(self, S):
		d = {}
		a = 0
		b = 0
		for i in S:
			if i in d:
				d[i] = d[i] + 1
			else:
				d[i] = 1
			if d[i] % 2 == 0:
				a += 1
		if a == len(S) // 2:
			return 1
		else:
			return 0


class Solution:

	def isPossible(self, S):
		ls = list(S)
		dic = {}
		for e in ls:
			try:
				count = dic[e]
				dic[e] = count + 1
			except:
				dic[e] = 1
		count = 0
		for (i, e) in dic.items():
			if e % 2 != 0:
				count += 1
		if count < 2:
			return 1
		return 0


class Solution:

	def isPossible(self, S):
		a = [0] * 256
		for i in S:
			x = ord(i)
			a[x] += 1
		count = 0
		for i in range(256):
			if a[i] % 2 != 0:
				count += 1
		if count > 1:
			return False
		else:
			return True


class Solution:

	def isPossible(self, S):
		S = S.lower()
		x = set(S)
		c = []
		for i in x:
			c.append(S.count(i))
		o = 0
		for i in c:
			if i & 1:
				o += 1
			if o > 1:
				return False
		return True


class Solution:

	def isPossible(self, S):
		freq = [0] * 26
		for i in S:
			freq[ord(i) - ord('a')] += 1
		odd = 0
		for i in freq:
			if i % 2:
				odd += 1
		return int(odd <= 1)


from collections import Counter

class Solution:

	def isPossible(self, S):
		freq = dict(Counter(S))
		is_odd = 0
		for (k, v) in freq.items():
			if v % 2 == 1:
				is_odd += 1
				if is_odd != 1 and is_odd != 0:
					return 0
		return 1


class Solution:

	def isPossible(self, S):
		arr = [0] * 26
		count = 0
		for i in S:
			arr[ord(i) - ord('a')] += 1
		for i in range(0, 26):
			if arr[i] % 2 != 0:
				count += 1
		if count < 2:
			return 1
		return 0


class Solution:

	def isPossible(self, S):
		d = dict()
		for c in S:
			if c not in d.keys():
				d[c] = 1
			else:
				d[c] += 1
		count = 0
		for k in d.keys():
			if d[k] % 2 != 0:
				count += 1
		if len(S) % 2 != 0 and count == 1:
			return True
		if len(S) % 2 == 0 and count == 0:
			return True
		else:
			return False


class Solution:

	def isPossible(self, S):
		arr = []
		n = len(S)
		for i in range(n):
			if S[i] in arr:
				arr.remove(S[i])
			else:
				arr.append(S[i])
		if len(arr) <= 1:
			return True
		else:
			return False


class Solution:

	def isPossible(self, ss):
		d = {}
		ss = ss.upper()
		f = 0
		for i in ss:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in d:
			if d[i] % 2 != 0:
				f += 1
		if f > 1:
			return 0
		else:
			return 1


class Solution:

	def isPossible(self, s):
		arr = []
		for i in range(len(s)):
			if s[i] in arr:
				arr.remove(s[i])
			else:
				arr.append(s[i])
		if len(s) % 2 == 0 and len(arr) == 0 or (len(s) % 2 == 1 and len(arr) == 1):
			return True
		else:
			return False


class Solution:

	def isPossible(self, S):
		hmap = {}
		oddcount = 0
		for i in S:
			if i in hmap:
				hmap[i] += 1
			else:
				hmap[i] = 1
		for i in hmap:
			if hmap[i] % 2 == 0:
				continue
			else:
				oddcount += 1
		if oddcount > 1:
			return False
		else:
			return True


class Solution:

	def isPossible(self, S):
		set_S = set(S)
		count = 0
		for i in set_S:
			if S.count(i) % 2 != 0:
				count += 1
			if count > 1:
				return 0
		return 1


class Solution:

	def isPossible(self, S):
		seti = set(S)
		odd = 0
		for i in seti:
			if S.count(i) % 2 != 0:
				odd += 1
		if odd > 1:
			return 0
		else:
			return 1


from collections import Counter

class Solution:

	def isPossible(self, S):
		c = Counter(S)
		a = []
		for i in c:
			a.append(c[i])
		d = 0
		for i in a:
			if i % 2 == 0:
				continue
			else:
				d += 1
		if d > 1:
			return False
		else:
			return True


class Solution:

	def isPossible(self, S):
		for i in S:
			if len(S) % 2 != 0:
				if sorted(S[:len(S) // 2]) == sorted(S[len(S) // 2 + 1:]):
					return 1
				else:
					return 0
			elif sorted(S[:len(S) // 2]) == sorted(S[len(S) // 2:]):
				return 1
			else:
				return 0


class Solution:

	def isPossible(self, s):
		hashmap = {}
		for i in s:
			if i in hashmap:
				hashmap[i] += 1
			else:
				hashmap[i] = 1
		l = []
		count = 0
		for i in hashmap.values():
			if i % 2 == 0:
				l.append(i)
			if i % 2 == 1 or i == 1:
				l.append(i)
				count += 1
				if count > 1:
					return False
		if len(l) == len(hashmap.values()):
			return True
		else:
			return False


class Solution:

	def isPossible(self, s):
		p = {}
		for i in s:
			if i not in p:
				p[i] = 1
			else:
				p[i] += 1
		x = 0
		for i in p:
			if p[i] % 2 != 0:
				x += 1
		if len(s) % 2 == 0 and x == 0:
			return True
		if len(s) % 2 != 0 and x == 1:
			return True
		else:
			return False


class Solution:

	def isPossible(self, s):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		f = False
		for i in d:
			if d[i] % 2 != 0:
				if f == False:
					f = True
				else:
					return False
		return True


class Solution:

	def isPossible(self, S):
		S = str(S)
		S == S[::-1]
		b = set(S)
		c = 0
		for i in b:
			if S.count(i) % 2 != 0:
				c += 1
		if c <= 1:
			return 'YES'


from collections import Counter

class Solution:

	def isPossible(self, S):
		c = Counter(S)
		c1 = 0
		for i in list(c.values()):
			if i % 2 != 0:
				c1 += 1
		if c1 < 2:
			return True