You are given an array A of strings.
A move onto S consists of swapping any two even indexed characters of S, or any two odd indexed characters of S.
Two strings S and T are special-equivalent if after any number of moves onto S, S == T.
For example, S = "zzxy" and T = "xyzz" are special-equivalent because we may make the moves "zzxy" -> "xzzy" -> "xyzz" that swap S[0] and S[2], then S[1] and S[3].
Now, a group of special-equivalent strings from A is a non-empty subset of A such that:

Every pair of strings in the group are special equivalent, and;
The group is the largest size possible (ie., there isn't a string S not in the group such that S is special equivalent to every string in the group)

Return the number of groups of special-equivalent strings from A.
 

Example 1:
Input: ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3
Explanation: 
One group is ["abcd", "cdab", "cbad"], since they are all pairwise special equivalent, and none of the other strings are all pairwise special equivalent to these.

The other two groups are ["xyzz", "zzxy"] and ["zzyx"].  Note that in particular, "zzxy" is not special equivalent to "zzyx".


Example 2:
Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3
 






Note:

1 <= A.length <= 1000
1 <= A[i].length <= 20
All A[i] have the same length.
All A[i] consist of only lowercase letters.

Source: leetcode | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: class Solution:
    def numSpecialEquivGroups(self, A: List[str]) -> int:
        

Solutions:
class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		return len(set((''.join(sorted(s[0::2])) + ''.join(sorted(s[1::2])) for s in A)))


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		signature = set()
		for (idx, s) in enumerate(A):
			signature.add(''.join(sorted(s[::2])) + ''.join(sorted(s[1::2])))
		return len(signature)


from collections import Counter

class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		count = Counter()
		for s in A:
			seven = ''
			sodd = ''
			for i in range(len(s)):
				if i % 2 == 0:
					seven += s[i]
				else:
					sodd += s[i]
			count[''.join(sorted(seven)), ''.join(sorted(sodd))] += 1
		return len(count)


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		for i in range(len(A)):
			A[i] = sorted(list(A[i][::2])) + sorted(list(A[i][1::2]))
		A.sort()
		n = 0
		while len(A) > 0:
			A = A[A.count(A[0]):]
			n += 1
		return n


from collections import Counter

class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		lst = []
		for word in A:
			evens = []
			odds = []
			for (i, l) in enumerate(word):
				if i % 2 == 0:
					evens.append(l)
				else:
					odds.append(l)
			lst.append((sorted(evens), sorted(odds)))
		s = []
		for word in lst:
			if word not in s:
				s.append(word)
		return len(s)


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		groups = []
		for s in A:
			info = (len(s), Counter(s[::2]), Counter(s[1::2]))
			if info not in groups:
				groups.append(info)
		return len(groups)


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		groups = []

		def match(string):
			(odds, evens) = ({}, {})
			for i in range(0, len(string), 2):
				evens[string[i]] = evens.get(string[i], 0) + 1
			for i in range(1, len(string), 2):
				odds[string[i]] = odds.get(string[i], 0) + 1
			for g in groups:
				if g[0] == odds and g[1] == evens:
					return (True, odds, evens)
			return (False, odds, evens)
		for s in A:
			(matched, odds, evens) = match(s)
			if not matched:
				groups.append((odds, evens))
		return len(groups)


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		group = list()
		count = 0
		for el in A:
			i = 0
			counter = {0: dict(), 1: dict()}
			for ch in el:
				if ch not in counter[i]:
					counter[i][ch] = 1
				else:
					counter[i][ch] += 1
				i = 1 - i
			if counter not in group:
				group.append(counter)
				count += 1
		return count


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		lst = [string2IndRes(string) for string in A]
		u_lst = unique(lst)
		return len(u_lst)

def string2IndRes(string):
	res = []
	for (i, c) in enumerate(string):
		res.append((c, i % 2))
	return Counter(res)

def unique(list1):
	unique_list = []
	for x in list1:
		if x not in unique_list:
			unique_list.append(x)
	return unique_list


from collections import defaultdict

class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		groups = []
		for word in A:
			result = {0: defaultdict(int), 1: defaultdict(int)}
			for (i, char) in enumerate(word):
				result[i % 2][char] += 1
			if result not in groups:
				groups.append(result)
		return len(groups)


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		even_set = []
		odd_set = []
		for i in A:
			even = []
			odd = []
			for j in range(len(i)):
				if j % 2 == 0:
					even.append(i[j])
				else:
					odd.append(i[j])
			even.sort()
			odd.sort()
			if even in even_set:
				k = []
				for (p, values) in enumerate(even_set):
					if even == values:
						k += [p]
				flag = 0
				for p in k:
					if odd_set[p] == odd:
						flag = 1
						break
				if flag == 0:
					even_set.append(even)
					odd_set.append(odd)
			else:
				even_set.append(even)
				odd_set.append(odd)
		return len(even_set)


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		haveList = list()
		ans = 0
		for i in range(len(A)):
			odd = dict()
			even = dict()
			for (y, v) in enumerate(A[i]):
				if y % 2 == 0:
					odd[v] = odd.get(v, 0) + 1
				else:
					even[v] = even.get(v, 0) + 1
			if [odd, even] not in haveList:
				haveList.append([odd, even])
		return len(haveList)


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		haveList = list()
		ans = 0
		for i in A:
			odd = dict()
			even = dict()
			for s in i[0::2]:
				odd[s] = odd.get(s, 0) + 1
			for s2 in i[1::2]:
				even[s2] = even.get(s2, 0) + 1
			if [odd, even] not in haveList:
				haveList.append([odd, even])
		length = len(haveList)
		return length


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		odds = []
		evens = []
		n = len(A[0])
		for s in A:
			de = {}
			do = {}
			for i in range(n):
				if i % 2:
					if s[i] in de:
						de[s[i]] += 1
					else:
						de[s[i]] = 1
				elif s[i] in do:
					do[s[i]] += 1
				else:
					do[s[i]] = 1
			odds.append(do)
			evens.append(de)
		total = []
		i = 0
		while i < len(odds):
			j = i + 1
			while j < len(odds):
				if odds[i] == odds[j] and evens[i] == evens[j]:
					odds.pop(j)
					evens.pop(j)
				else:
					j += 1
			i += 1
		return len(odds)


from collections import Counter

class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		n = len(A)
		groups = 0
		taken = [0] * n
		even_counters = list(map(Counter, [z[::2] for z in A]))
		odd_counters = list(map(Counter, [z[1::2] for z in A]))
		for i in range(n):
			if taken[i] == 0:
				oci = odd_counters[i]
				eci = even_counters[i]
				for j in range(i + 1, n):
					if taken[j] == 1:
						continue
					ocj = odd_counters[j]
					ecj = even_counters[j]
					if oci == ocj and eci == ecj:
						taken[j] = 1
				groups += 1
		return groups


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		(res, count, ct) = (0, [], collections.Counter)
		for s in A:
			even = collections.defaultdict(int)
			odd = collections.defaultdict(int)
			isEven = True
			for c in s:
				if isEven:
					even[c] += 1
				else:
					odd[c] += 1
				isEven = not isEven
			count.append((even, odd))
		i = 0
		while i < len(count):
			j = i + 1
			while j < len(count):
				if count[i][0] == count[j][0] and count[i][1] == count[j][1]:
					count.pop(j)
					j -= 1
				j += 1
			res += 1
			count.pop(i)
		return res


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		(res, count, ct) = (0, [], collections.Counter)
		for s in A:
			even = collections.defaultdict(int)
			odd = collections.defaultdict(int)
			isEven = True
			for c in s:
				if isEven:
					even[c] += 1
				else:
					odd[c] += 1
				isEven = not isEven
			count.append((even, odd))
		while count:
			(i, count2) = (1, [])
			for i in range(1, len(count)):
				if count[0][0] != count[i][0] or count[0][1] != count[i][1]:
					count2.append(count[i])
			res += 1
			count = count2
		return res


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		if len(A) == 1:
			return 1

		def areSpecialEquiv(x: str, y: str) -> bool:
			dic_x = {}
			dic_y = {}
			for c in x:
				if c not in y:
					return False
			for i in range(len(x)):
				found = 0
				for j in range(len(y)):
					if x[i] == y[j] and i % 2 == j % 2:
						found = 1
				if not found:
					return False
			for l in x:
				if l in dic_x:
					dic_x[l] += 1
				else:
					dic_x[l] = 1
			for l in y:
				if l in dic_y:
					dic_y[l] += 1
				else:
					dic_y[l] = 1
			for l in dic_x:
				if dic_x[l] != dic_y[l]:
					return False
			return True
		stack = A[:]
		arr = []
		while stack:
			arr2 = []
			curr = stack.pop(0)
			count = 1
			for w in stack:
				if areSpecialEquiv(curr, w):
					count += 1
					arr2.append(w)
			arr.append(count)
			for i in arr2:
				stack.remove(i)
		return len(arr)


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		counter_list = set()
		for i in A:
			even = []
			odd = []
			for (index, item) in enumerate(i):
				if index % 2 == 0:
					even.append(item)
				else:
					odd.append(item)
			normalised = ''.join(sorted(even) + sorted(odd))
			counter_list.add(normalised)
		return len(counter_list)


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		l = len(A)
		counter = {}
		for i in range(l):
			odd = []
			even = []
			for j in range(len(A[i])):
				if j % 2 == 0:
					even.append(A[i][j])
				else:
					odd.append(A[i][j])
			even.sort()
			odd.sort()
			counter[str(even), str(odd)] = counter.get((str(even), str(odd)), 0) + 1
		return len(counter)


class Solution:

	def numSpecialEquivGroups(self, A: List[str]) -> int:
		d = set()
		for w in A:
			even = ''.join(sorted(w[0::2]))
			odd = ''.join(sorted(w[1::2]))
			d.add((even, odd))
		return len(d)