## 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` and `S`, then `S` and `S`.

Now, a group of special-equivalent strings from `A` is a non-empty subset of A such that:

1. Every pair of strings in the group are special equivalent, and;
2. 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.

## 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);