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].

Example 1:

`Input: ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]` Output: 3

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.

Straightforward Solution `Special equivalent`

means two string have the same char set on even and odd positions. So we compare all the pairs of array.

`is_same`

use two arrays to store the chars count of strings.

Time complexity is O(N^2 * 26).

class Solution {public : bool is_same (string A, string B) { vector <int > count_odd (26 , 0 ) ; vector <int > count_eve (26 , 0 ) ; for (int i=0 ; i<A.size(); i++) { if (i%2 ) count_odd[A[i]-'a' ]++; else count_eve[A[i]-'a' ]++; } for (int i=0 ; i<B.size(); i++) { if (i%2 ) count_odd[B[i]-'a' ]--; else count_eve[B[i]-'a' ]--; } for (int i=0 ; i<26 ; i++) { if (count_odd[i] || count_eve[i]) return false ; } return true ; } int numSpecialEquivGroups (vector <string >& A) { int flag[A.size()]; for (int i=0 ; i<A.size(); i++) flag[i] = i; for (int i=0 ; i<A.size(); i++) { int x = flag[i]; if (x != i) continue ; for (int j=i+1 ; j < A.size(); j++) { int y = flag[j]; if (y != j) continue ; if (is_same(A[x], A[y])) { flag[y] = x; } } } set <int > s; for (int i=0 ; i<A.size(); i++) s.insert(flag[i]); return s.size(); } };

Sort based on index and add to Set Another simpler method to check whether two string is `special equivalent`

is split a string into the odd part and even part, then sort two parts separately and combine into a new string.

Time complexity is O(N* M*log(M)), where `M`

is the max length of string.

class Solution {public : string convert (string str) { string odd; string even; for (int i=0 ; i<str.size(); i++) i%2 == 0 ? odd += str[i] : even += str[i]; sort(odd.begin(), odd.end()); sort(even.begin(), even.end()); return even + odd; } int numSpecialEquivGroups (vector <string >& A) { set <string > S; for (int i=0 ; i<A.size(); i++) S.insert(convert(A[i])); return S.size(); } };

One line Python solution `str[::2]`

can filter all chars at even positions, and `str[1::2]`

will filter all chars in odd positions.

class Solution : def numSpecialEquivGroups (self, A: List[str ] ) -> int: return len ({('' .join(sorted (str [::2 ]) +sorted (str [1 ::2 ]))) for str in A})