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.

Difficulty: introductory

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()
        
        # Use pair of sorted even substring and odd substring as unique key
        
        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
        # print(count.keys())
        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:
        return len(set(''.join(sorted(a[::2])) + ''.join(sorted(a[1::2])) for a in A))


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): 
  
    # intilize a null list 
    unique_list = [] 
      
    # traverse for all elements 
    for x in list1: 
        # check if exists in unique_list or not 
        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:
        
        # set1 = set()
        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:
        
        set1 = set()
        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 
                if flag == 0:
                    even_set.append(even) 
                    odd_set.append(odd)
            else:
                even_set.append(even) 
                odd_set.append(odd)
                
        print((even_set,odd_set))
        return len(even_set)
            
                
                
                
                


class Solution:
    def numSpecialEquivGroups(self, A: List[str]) -> int:
        group = []
        
        for el in A:
            i = 0
            # counter = {0: dict(), 1: dict()}
            counter = [dict(), 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)
        
        return len(group)
            
            
            
            
        


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:
        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:
        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
                else:
                    if 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:
        s = set()
        for a in A:
            s.add(''.join(sorted(a[::2])) + ''.join(sorted(a[1::2])))
        return len(s)
        
        
#         dic = Counter()
        
#         def idx(x):
#             ans = \"\"
#             for k in sorted(x):
#                 ans += k + str(x[k])
#             return ans
        
#         for a in A:
#             odd = Counter(a[1::2])
#             even = Counter(a[::2])
#             dic[idx(odd), idx(even)] += 1
            
#         return len(dic)
            
        
            
            


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)