MediumNo. 0893
Groups of Special-Equivalent Strings — LeetCode 893 Python Solution
- Pattern
- Sorting
- Topics
- Array, Hash Table, String, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an array of strings of the same length words. In one move, you can swap any two even indexed characters or any two odd indexed characters of a string words[i].
Example
- Input
- words = ["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 is all pairwise special equivalent to these.
Python solution
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)Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 893. Groups of Special-Equivalent Strings is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0049 | Group Anagrams | Medium |
| 0522 | Longest Uncommon Subsequence II | Medium |
| 0692 | Top K Frequent Words | Medium |
| 0720 | Longest Word in Dictionary | Medium |
| 0721 | Accounts Merge | Medium |
| 0792 | Number of Matching Subsequences | Medium |
Frequently asked questions
- How hard is LeetCode 893. Groups of Special-Equivalent Strings?
LeetCode 893. Groups of Special-Equivalent Strings is rated Medium on LeetCode.
- What is the time complexity of LeetCode 893. Groups of Special-Equivalent Strings?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 893. Groups of Special-Equivalent Strings?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 893. Groups of Special-Equivalent Strings cover?
LeetCode 893. Groups of Special-Equivalent Strings is tagged Array, Hash Table, String and Sorting on LeetCode.