0893-特殊等价字符串组

给你一个字符串数组 words。

一步操作中，你可以交换字符串 words[i] 的任意两个偶数下标对应的字符或任意两个奇数下标对应的字符。

对两个字符串 words[i] 和 words[j] 而言，如果经过任意次数的操作，words[i] == words[j]
，那么这两个字符串是 特殊等价 的。

• 例如，words[i] = "zzxy" 和 words[j] = "xyzz" 是一对 特殊等价 字符串，因为可以按 "zzxy" -> "xzzy" -> "xyzz" 的操作路径使 words[i] == words[j] 。

现在规定， **words **的 一组特殊等价字符串 就是 words 的一个同时满足下述条件的非空子集：

• 该组中的每一对字符串都是 特殊等价 的
• 该组字符串已经涵盖了该类别中的所有特殊等价字符串，容量达到理论上的最大值（也就是说，如果一个字符串不在该组中，那么这个字符串就 不会 与该组内任何字符串特殊等价）

返回 words 中 特殊等价字符串组 的数量。

示例 1：

**输入：** words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
**输出：** 3
**解释：**
其中一组为 ["abcd", "cdab", "cbad"]，因为它们是成对的特殊等价字符串，且没有其他字符串与这些字符串特殊等价。
另外两组分别是 ["xyzz", "zzxy"] 和 ["zzyx"]。特别需要注意的是，"zzxy" 不与 "zzyx" 特殊等价。

示例 2：

**输入：** words = ["abc","acb","bac","bca","cab","cba"]
**输出：** 3
**解释：** 3 组 ["abc","cba"]，["acb","bca"]，["bac","cab"]

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 20
• 所有 words[i] 都只由小写字母组成。
• 所有 words[i] 都具有相同的长度。

方法：计数

思路和算法

让我们试着表述一个特殊等价的字符串 S，通过找到函数 \mathcal{C 使得 S \equiv T \iff \mathcal{C}(S) = \mathcal{C}(T)。

通过交换，我们可以排列偶数索引字母和奇数索引字母。这些排列的特征在于字母的数量：所有这样的排列都有相同的数量，不同的数量会产生不同的排列。

因此，函数 \mathcal{C}(S) =（S 中偶数索引字母的数量，其后是 S 中奇数索引字母的数量）成功地刻画了这一等价关系。

然后，我们统计出满足 S \in A 的 \mathcal{C}(S) 的数量。

[mfQicAZA-Java]

class Solution {
    public int numSpecialEquivGroups(String[] A) {
        Set<String> seen = new HashSet();
        for (String S: A) {
            int[] count = new int[52];
            for (int i = 0; i < S.length(); ++i)
                count[S.charAt(i) - 'a' + 26 * (i % 2)]++;
            seen.add(Arrays.toString(count));
        }
        return seen.size();
    }
}

[mfQicAZA-Python]

class Solution(object):
    def numSpecialEquivGroups(self, A):
        def count(A):
            ans = [0] * 52
            for i, letter in enumerate(A):
                ans[ord(letter) - ord('a') + 26 * (i%2)] += 1
            return tuple(ans)

        return len({count(word) for word in A})

复杂度分析

• 时间复杂度：O(\sum\limits_{i} (A_i)\text{.length})。

• 空间复杂度：O(N)，其中 N 是 A 的长度。