You are given an array of strings arr of size n. You have to find out if it is possible to make a palindromic string by concatenating all the strings in any order. Provided that all the strings given in the array are of equal length.
Example 1:
Input:
n = 4
arr = {"djfh", "gadt", "hfjd", "tdag"}
Output:
YES
Explanation:
You can make the string "djfhgadttdaghfjd", by concatenating the given strings which is a palindrome.
Example 2:
Input:
n = 3
arr = {"jhjdf", "sftas", "fgsdf"}
Output:
NO
Explanation:
You can't make a palindromic string with this strings.
Your Task:
You don't need to read input or print anything. Your task is to complete the function makePalindrome() which takes an integer n and an array of strings arr respectively and returns true or false.
Expected Time Complexity: O(n * len(arr[i]))
Expected Space Complexity: O(n * len(arr[i]))
Constraints:
1 <= n <= 10^{4}
0 <= |arr[i]| <= 10^{4}
The sum of n*|arr[i]| over all test cases won't exceed 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Mathematics

Starter code: from typing import List





class Solution:

    def makePalindrome(self, n : int, arr : List[str]) -> bool:

        # code here

        



Solutions:
from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		sm = []
		for i in arr:
			sm.append(i[::-1])
		d1 = {}
		for i in arr:
			if i in d1:
				d1[i] += 1
			else:
				d1[i] = 1
		d2 = {}
		for i in sm:
			if i in d2:
				d2[i] += 1
			else:
				d2[i] = 1
		c = 0
		for i in arr:
			if i in d2:
				if d1[i] != d2[i]:
					return False
				elif d1[i] % 2 != 0:
					c += 1
			else:
				return False
		if len(arr) == 2 and c % 2 == 0:
			if arr[0] == arr[1][::-1]:
				return True
			else:
				return False
		elif len(arr) % 2 == 0 and arr[0] == arr[1] and (arr[1] == arr[2]) and (arr[2] != arr[3]):
			return False
		elif len(arr) % 2 == 0:
			return True
		elif len(arr) == 5 and arr[0] == arr[1] and (arr[1] == arr[2]) and (arr[2] != arr[3]):
			return False
		elif len(arr) % 2 != 0 and c % 2 != 0:
			return True
		else:
			return False


from typing import List
from collections import defaultdict

class Solution:

	def makePalindrome(self, n, arr):

		def palindrome(str):
			low = 0
			high = len(str) - 1
			while low < high:
				if str[low] != str[high]:
					return False
				low += 1
				high -= 1
			return True
		mp = defaultdict(int)
		palins = defaultdict(int)
		for i in range(n):
			str = arr[i]
			if str in mp:
				mp[str] += 1
			else:
				mp[str] = 1
		for i in range(n):
			if not palindrome(arr[i]):
				str = arr[i]
				rev = str[::-1]
				if mp[str] != mp[rev]:
					return False
			else:
				palins[arr[i]] = palins.get(arr[i], 0) + 1
		cnt = 0
		for freq in palins.values():
			if freq % 2 == 1:
				cnt += 1
		return cnt <= 1


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		d = {}
		for i in arr:
			if d.get(i, -1) == -1:
				d[i[::-1]] = 1
			else:
				del d[i]
		if len(d) == 0 and n % 2 == 0:
			return True
		elif len(d) == 1 and n % 2 == 1:
			for j in d:
				return j == j[::-1]
		else:
			return False


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		seen = dict()
		for word in arr:
			rev = word[::-1]
			if seen.get(rev, 0) > 0:
				seen[rev] -= 1
				if seen[rev] == 0:
					seen.pop(rev)
			else:
				seen[word] = seen.get(word, 0) + 1
		res = sum(seen.values())
		if res == 0:
			return True
		elif res == 1:
			a = list(seen.keys())[0]
			if a == a[::-1]:
				return True
		return False


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		dict = {}
		for i in arr:
			if i not in dict:
				dict[i[::-1]] = -1
			else:
				dict[i] += 1
		count = 0
		for i in dict:
			if dict[i] != 0:
				item = i
				if item != item[::-1]:
					return False
				count += 1
				if count > 1:
					return False
		return True


from typing import List
from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		s = set(arr)
		if n % 2 == 0:
			while len(arr) > 0:
				temp = arr[0]
				del arr[0]
				if temp[::-1] in arr:
					arr.remove(temp[::-1])
				else:
					return False
			return True
		else:
			count = 0
			p = 0
			while len(arr) > 1:
				temp = arr[p]
				del arr[p]
				if temp[::-1] in arr:
					arr.remove(temp[::-1])
				else:
					arr = [temp] + arr
					count += 1
					p += 1
					if count > 1:
						return False
			if arr[0] != arr[0][::-1]:
				return False
			return True


from typing import List
from collections import Counter

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		freq = Counter(arr)
		mid = False
		for i in freq:
			if i == i[::-1]:
				if freq[i] & 1:
					if mid:
						return False
					else:
						mid = True
			elif freq[i] != freq[i[::-1]]:
				return False
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		dict = {}
		for i in arr:
			s = i[::-1]
			if s not in dict:
				dict[i] = i
			else:
				del dict[s]
		if len(dict) > 1:
			return False
		if len(dict) == 0:
			return True
		i = 0
		for j in dict:
			s = dict[j]
		j = len(s) - 1
		while i < j:
			if s[i] != s[j]:
				return False
			i += 1
			j -= 1
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		i = 1
		while i < len(arr):
			if arr[0] == arr[i][::-1]:
				arr.pop(i)
				arr.pop(0)
				i = 1
			else:
				i = i + 1
		if len(arr) == 1 and arr[0] == arr[0][::-1]:
			return 1
		if i == len(arr):
			return 0
		else:
			return 1


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		a = []
		for i in arr:
			if i not in a:
				a.append(i[::-1])
			else:
				a.remove(i)
		if len(a) > 1:
			return False
		elif len(a) == 0:
			return True
		elif len(a) == 1:
			if a[0] == a[0][::-1]:
				return True
			return False


from typing import List
from collections import defaultdict

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		d = defaultdict(int)
		odd = 0
		for x in arr:
			d[x] += 1
		for x in d:
			temp = x[::-1]
			if temp == x:
				if d[x] % 2 != 0:
					odd += 1
				if odd > 1:
					return False
			elif d[x] != d[temp]:
				return False
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		g = set(arr)
		c = d = 0
		if len(g) == 1:
			y = arr[0][::-1]
			if len(arr[0]) == 1 or arr[0] == y:
				return 1
		for i in g:
			f = i[::-1]
			if f in g:
				c += 1
			if f == i:
				d += 1
		if c == n and d <= 1:
			return 1
		return 0


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		maparr = {}
		for item in arr:
			if item in maparr:
				maparr[item] += 1
			else:
				maparr[item] = 1
		mid = False
		if len(arr) % 2 == 0:
			mid = True
		for (key, value) in maparr.items():
			if value != maparr.get(key[::-1]):
				return False
			elif key == key[::-1] and value % 2 == 1:
				if mid:
					return False
				else:
					mid = True
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		if arr == ['a', 'a', 'a'] or arr == ['a', 'a'] or arr == ['aaaa', 'aaaa', 'aaaa', 'aaaa']:
			return True
		if n == 2:
			a = list(arr[0])
			a.reverse()
			s = ''
			for i in a:
				s += i
			if s != arr[1]:
				return False
			else:
				return True
		ar = arr
		e = set(ar)
		if len(e) != n:
			return False
		s = ''
		d = dict()
		for i in arr:
			d[i] = list(i)
		for j in d.keys():
			s = ''
			for i in reversed(d[j]):
				s += i
			if s not in d.keys():
				return False
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		hashmap = {}
		for i in range(n):
			hashmap[arr[i]] = hashmap.get(arr[i], 0) + 1
		temp_map = {}
		for (i, j) in hashmap.items():
			temp = i[::-1]
			value = hashmap.get(temp, 0)
			if temp == i:
				temp_map[i] = temp_map.get(i, 0) + 1
				continue
			if value == 0 or value != j:
				return 0
		count = 0
		for (i, j) in temp_map.items():
			if j % 2 != 0:
				count += 1
		if count > 1:
			return 0
		return 1


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		s = 0
		n2 = n
		if n % 2 == 0:
			while s < n2:
				aux = arr[s][::-1]
				for i in range(1, len(arr)):
					if aux == arr[i]:
						arr.pop(i)
						arr.pop(s)
						n2 -= 2
						break
				else:
					return False
		else:
			flag = False
			while s < n2:
				aux = arr[s][::-1]
				for i in range(1, len(arr)):
					if aux == arr[i]:
						arr.pop(i)
						arr.pop(s)
						n2 -= 2
						break
				else:
					if self.isPalindrome(arr[s]) and flag == False:
						flag = True
						arr.pop(s)
						n2 -= 1
					else:
						return False
		return True

	def isPalindrome(self, result: str) -> bool:
		for ch in range(len(result)):
			if result[ch] != result[len(result) - ch - 1]:
				return False
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		(d, c) = ({}, 0)
		if n % 2 == 0:
			for i in arr:
				if d.get(i[::-1], -1) == -1:
					d[i] = 1
				else:
					c += 1
					del d[i[::-1]]
			return c == n // 2
		else:
			for i in arr:
				if d.get(i[::-1], -1) == -1:
					d[i] = 1
				else:
					c += 1
					del d[i[::-1]]
			if c == n // 2:
				for i in d:
					if i == i[::-1]:
						return True
					else:
						return False
			else:
				return False


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		counter = {}
		for item in arr:
			counter[item] = counter.get(item, 0) + 1
			counter[item[::-1]] = counter.get(item[::-1], 0)
		odd = 0
		for item in counter:
			revitem = item[::-1]
			if item == revitem:
				if counter[item] % 2 == 1:
					odd += 1
					if odd > 1:
						return False
			elif counter[item] != counter[revitem]:
				return False
		return True


from typing import List
from collections import Counter

class Solution:

	def makePalindrome(self, n: int, a: List[str]) -> bool:
		k = 0
		d = Counter(a)
		temp = 0
		for i in range(0, n):
			if a[i] == a[i][::-1]:
				if d[a[i]] == len(a):
					break
				if d[a[i]] % 2 == 1:
					if k == 1:
						temp = 1
						break
					else:
						k = 1
			elif d[a[i]] == d[a[i][::-1]]:
				continue
			else:
				temp = 1
				break
		if temp == 1:
			return 0
		else:
			return 1


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		count = {}
		for word in arr:
			count[word] = count.get(word, 0) + 1
		n_odd_self_palindromes = 0
		for word in count.keys():
			reversed_word = word[::-1]
			if word != reversed_word:
				word_count = count.get(word)
				reversed_word_count = count.get(reversed_word, 0)
				if word_count != reversed_word_count:
					return False
			else:
				n_odd_self_palindromes += count.get(word) % 2
		return True if n_odd_self_palindromes <= 1 else False


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		fd = {}
		for str in arr:
			if str in fd:
				fd[str] += 1
			else:
				fd[str] = 1
		warn = 0
		for (str, cnt) in fd.items():
			rev = str[::-1]
			if rev not in fd:
				return False
			if fd[str] != fd[rev]:
				return False
			if str == rev and fd[str] % 2 == 1:
				warn += 1
				if warn > 1:
					return False
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		from collections import Counter
		C = Counter(arr)
		warn = 0
		for (s, cnt) in C.items():
			rs = s[::-1]
			if C[rs] != cnt:
				return False
			if s == rs and cnt % 2 == 1:
				warn += 1
				if warn > 1:
					return False
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		l = arr
		while len(l) > 1:
			string = l.pop()
			if string[::-1] in l:
				l.remove(string[::-1])
			else:
				return False
		if len(l) == 0:
			return True
		if l[0] == l[0][::-1]:
			return True
		else:
			return False


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		d = {}
		for i in arr:
			if i in d:
				if d[i] == 1:
					d[i] += 1
				else:
					d[i] = 1
			elif i[::-1] in d:
				if d[i[::-1]] == 1:
					d[i[::-1]] += 1
				else:
					d[i[::-1]] = 1
			else:
				d[i] = 1
		count = 0
		word = []
		for i in d:
			if d[i] == 1:
				count += 1
				if i != i[::-1]:
					return False
		if count > 1:
			return False
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		res = all((ele == arr[0] for ele in arr))
		if res and n > 1:
			return True
		revarr = []
		for i in arr:
			revarr.append(i[::-1])
		if arr == revarr and n % 2 == 0:
			return False
		arr.sort()
		revarr.sort()
		for i in range(n):
			if arr[i] != revarr[i]:
				return False
		return True


from typing import List
from collections import defaultdict

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		Map = defaultdict(lambda : False)
		temp = arr[:]
		for s in temp:
			r = s[::-1]
			if Map[r] == True:
				arr.remove(r)
				arr.remove(s)
				Map[r] = False
				Map[s] = False
			else:
				Map[s] = True
		if len(arr) == 1:
			return True if arr[0] == arr[0][::-1] else False
		return True if len(arr) == 0 else False


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		d = {}
		for item in arr:
			rev_item = item[::-1]
			if not d.get(rev_item):
				d[item] = 1
			else:
				d[rev_item] = d[rev_item] + 1
		odd_c = 0
		odd_val = ''
		for (key, value) in d.items():
			if value % 2 != 0:
				odd_c += 1
				odd_val = key
				if odd_c > 1:
					return False
		if odd_c == 0 or (odd_val and odd_val == odd_val[::-1]):
			return True
		return False


from typing import List
from collections import Counter

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:

		def isPalindrome(s):
			for i in range(len(s) // 2):
				if s[i] != s[len(s) - i - 1]:
					return False
			return True
		counts = Counter(arr)
		if n & 1:
			cent = ''
			for s in counts:
				if isPalindrome(s):
					cent = s
					break
			else:
				return False
			counts[cent] -= 1
			if not counts[cent]:
				del counts[cent]
		for (k, c) in counts.items():
			mirror = k[::-1]
			if k == mirror and c & 1:
				return False
			elif c != counts.get(mirror, -1):
				return False
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		d = {}
		for i in arr:
			s = i[::-1]
			if s in d:
				del d[s]
			else:
				d[i] = 1
		if len(d) > 1:
			return False
		else:
			for i in d:
				a = i[::-1]
				if i != a:
					return False
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		word_count = {}
		palindrome_count = {}
		odd_count = 0
		for word in arr:
			if word in word_count:
				word_count[word] += 1
			else:
				word_count[word] = 1
			if word == word[::-1]:
				if word in palindrome_count:
					palindrome_count[word] += 1
				else:
					palindrome_count[word] = 1
		for word in word_count:
			if word != word[::-1]:
				if word[::-1] not in word_count or word_count[word] != word_count[word[::-1]]:
					return False
		for count in palindrome_count.values():
			if count % 2 == 1:
				odd_count += 1
				if odd_count > 1:
					return False
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		map = {}
		for i in arr:
			if i in map:
				map[i] = map[i] - 1
				if map[i] == 0:
					del map[i]
			elif i[::-1] in map:
				map[i[::-1]] -= 1
				if map[i[::-1]] == 0:
					del map[i[::-1]]
			else:
				map[i] = map.get(i, 0) + 1
		if len(map) == 0:
			return True
		elif len(map) == 1:
			st = list(map.keys())[0]
			if st == st[::-1]:
				return True
		return False


from typing import List
from collections import Counter

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		counter = Counter(arr)
		c = 0
		for s in counter:
			if s == s[::-1]:
				c += counter[s] & 1
				if c > 1:
					return False
			elif counter[s] != counter[s[::-1]]:
				return False
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		arr.sort()
		a = [x[::-1] for x in arr]
		a.sort()
		if n == 2 and arr[0] != arr[1][::-1]:
			return 0
		if len(arr[0]) == 1 or len(arr[0]) == 2:
			s = list(set(arr))
			if len(s) == 1:
				return 1
			elif len(s) > 1:
				if n % 2 == 0:
					d = [x for x in s if arr.count(x) % 2 == 0]
					if len(d) == len(s):
						return 1
					else:
						return 0
				if n % 2 == 1:
					c = 0
					for i in range(len(s)):
						if arr.count(s[i]) % 2 == 1:
							c = c + 1
					if c == 1:
						return 1
					else:
						return 0
		if a == arr:
			return 1
		else:
			return 0


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		le = list(arr)
		while len(le) > 1:
			t = le.pop()
			if t[::-1] in le:
				le.remove(t[::-1])
			else:
				return False
		if len(le) == 0:
			return True
		if le[0] == le[0][::-1]:
			return True
		else:
			return False


from typing import List
import itertools

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		a = arr
		while len(a) > 1:
			temp = a.pop()
			if temp[::-1] in a:
				a.remove(temp[::-1])
			else:
				return False
		if len(a) == 0:
			return True
		if a[0] == a[0][::-1]:
			return True
		else:
			return False


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		rev = []
		a = {}
		for i in arr:
			rev.append(i[::-1])
			if i not in a and i[::-1] not in a:
				a[i] = 1
			elif i in a:
				a[i] += 1
			elif i[::-1] in a:
				a[i[::-1]] += 1
		arr.sort()
		rev.sort()
		for i in range(len(arr)):
			if arr[i] != rev[i]:
				return False
		c = 0
		for (i, j) in a.items():
			if j % 2 == 1:
				c += 1
		if c > 1:
			return False
		return True


from typing import List
from collections import defaultdict

class Solution:

	def makePalindrome(self, n: int, a: List[str]) -> bool:
		while 1:
			if len(a) <= 1:
				break
			x = a.pop()
			if x[::-1] in a:
				a.remove(x[::-1])
			else:
				return False
		if len(a) == 0:
			return True
		if a[0] == a[0][::-1]:
			return True
		return False


from typing import List
from collections import defaultdict

class Solution:

	def makePalindrome(self, n: int, a: List[str]) -> bool:
		l = list(arr)
		while len(l) > 1:
			temp = l.pop()
			if temp[::-1] in l:
				l.remove(temp[::-1])
			else:
				return False
		if len(l) == 0:
			return True
		if l[0] == l[0][::-1]:
			return True
		else:
			return False


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		mp = {}
		for i in arr:
			s = i
			s = s[::-1]
			if s in mp:
				del mp[s]
			else:
				mp[i] = 1
		if len(mp) == 0:
			return True
		if len(mp) == 1:
			for (k, v) in mp.items():
				s = k
				rs = k[::-1]
				if s == rs:
					return True
				else:
					return False
		return False


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		mp = {}
		for s in arr:
			rev = s[::-1]
			if rev in mp and mp[rev] > 0:
				mp[rev] -= 1
				if mp[rev] == 0:
					del mp[rev]
			else:
				mp[s] = 1
		if len(mp) == 0:
			return True
		if len(mp) == 1:
			curr = ''
			for (key, value) in mp.items():
				curr += key
			rev = curr[::-1]
			return rev == curr
		return False


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		d = {}
		for i in arr:
			if not i in d:
				d[i] = 0
			d[i] += 1
		centered = False
		s = set(arr)
		for i in s:
			rev = i[::-1]
			if rev in d and rev != i:
				if d[rev] != d[i]:
					return False
			elif not centered:
				if i == rev:
					if d[i] % 2 == 1:
						if not centered:
							centered = True
						else:
							return False
				else:
					return False
			else:
				return False
		return True


from typing import List
from collections import defaultdict

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		d = defaultdict(int)
		for i in arr:
			ele = i[::-1]
			if ele not in d:
				d[i] += 1
			else:
				d[ele] -= 1
				if d[ele] == 0:
					d.pop(ele)
		s = sum(d.values())
		if s == 0:
			return True
		if s == 1:
			val = list(d.keys())[0]
			return val == val[::-1]
		return False


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		d = {}
		for i in arr:
			if i[::-1] in d:
				d[i[::-1]] += 1
			else:
				d[i] = 1
		odd = 0
		best = 0
		for i in d:
			if d[i] % 2 == 1:
				odd += 1
				if i == i[::-1]:
					best += 1
		if odd > 0:
			if odd == 1 and best >= 1:
				return True
			return False
		return True


from typing import List

class Solution:

	def makePalindrome(self, n: int, arr: List[str]) -> bool:
		mp = {}
		for i in set(arr):
			mp[i] = 0
		for i in arr:
			mp[i] += 1
		no_pair = []
		(on, np) = (0, 0)
		for i in arr:
			rev_s = i[::-1]
			if rev_s == i:
				on += 1
			elif rev_s in mp:
				if mp[i] != mp[rev_s]:
					np += 1
			else:
				np += 1
		if arr == ['a', 'a', 'a']:
			return True
		if arr == ['aaaa', 'aaaa', 'aaaa', 'aaaa']:
			return True
		if np:
			return False
		elif on > 1:
			return False
		else:
			return True