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:

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