What defines a special-equivalent string in this problem?

Two strings are special-equivalent if you can swap any even-indexed characters or any odd-indexed characters to make them identical.

Why do we sort even and odd indices separately?

Sorting ensures all strings that can transform into each other through allowed swaps produce the same normalized key for hashing.

Can this approach handle arrays with 1000 strings of length 20?

Yes, because it scans each string once and uses hash sets, keeping operations within acceptable time and space limits.

Is pairwise comparison necessary to determine groups?

No, using normalized keys with hash sets eliminates the need for O(N^2) pairwise checks.

How does this solution tie to the 'Array scanning plus hash lookup' pattern?

It scans each array element once to compute a key and uses a hash lookup to track unique groups efficiently, matching the pattern.

#893

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

特殊等价字符串组

给你一个字符串数组 words 。一步操作中，你可以交换字符串 words[i] 的任意两个偶数下标对应的字符或任意两个奇数下标对应的字符。对两个字符串 words[i] 和 words[j] 而言，如果经过任意次数的操作， words[i] == words[j] ，那么这两个字符串是特殊等…

数组哈希表字符串排序

题目描述

给你一个字符串数组 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] 都具有相同的长度。

lightbulb

解题思路

方法一

1

2

3

4

5

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

speed

复杂度分析

指标	值
时间	complexity is O(N * L log L), where N is the number of strings and L is the string length due to sorting characters at even and odd indices. Space complexity is O(N * L) to store normalized keys in the hash set.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on array scanning rather than naive pairwise string comparison.
question_mark
Look for efficient grouping using hash-based normalization.
question_mark
Be prepared to explain why sorting even and odd characters separately guarantees correctness.

warning

常见陷阱

外企场景

error
Attempting pairwise comparisons between all strings leading to O(N^2) time.
error
Failing to separate even and odd indices when generating keys.
error
Assuming identical sorted full strings is sufficient for equivalence.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider strings of varying lengths and how normalization would change.
arrow_right_alt
Compute group sizes instead of just the number of groups.
arrow_right_alt
Count groups under additional constraints, such as limiting moves.

help

常见问题

外企场景

继续练习

#833 字符串中的查找与替换 #792 匹配子序列的单词数 #1048 最长字符串链