## 893. Groups of Special-Equivalent Strings

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:3Explanation: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.

## Rust Solution

```
struct Solution;
use std::collections::BTreeMap;
use std::collections::HashSet;
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
struct Count {
even: BTreeMap<char, usize>,
odd: BTreeMap<char, usize>,
}
impl Count {
fn new(s: String) -> Self {
let mut even: BTreeMap<char, usize> = BTreeMap::new();
let mut odd: BTreeMap<char, usize> = BTreeMap::new();
for (i, c) in s.chars().enumerate() {
if i % 2 == 0 {
*even.entry(c).or_default() += 1;
} else {
*odd.entry(c).or_default() += 1;
}
}
Count { even, odd }
}
}
impl Solution {
fn num_special_equiv_groups(a: Vec<String>) -> i32 {
let mut hs: HashSet<Count> = HashSet::new();
for s in a {
hs.insert(Count::new(s));
}
hs.len() as i32
}
}
#[test]
fn test() {
let a: Vec<String> = vec_string!["a", "b", "c", "a", "c", "c"];
assert_eq!(Solution::num_special_equiv_groups(a), 3);
let a: Vec<String> = vec_string!["aa", "bb", "ab", "ba"];
assert_eq!(Solution::num_special_equiv_groups(a), 4);
let a: Vec<String> = vec_string!["abc", "acb", "bac", "bca", "cab", "cba"];
assert_eq!(Solution::num_special_equiv_groups(a), 3);
let a: Vec<String> = vec_string!["abcd", "cdab", "adcb", "cbad"];
assert_eq!(Solution::num_special_equiv_groups(a), 1);
}
```

Having problems with this solution? Click here to submit an issue on github.