Groups of Special-Equivalent Strings

LeetCode 893, Medium. Topics: Array, Hash Table, String, Sorting. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 25 parametrized pytest cases, and a playground notebook:

lcpy gen -n 893   # by problem number
lcpy gen -s groups_of_special_equivalent_strings   # by problem name

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]. Two strings words[i] and words[j] are special-equivalent if after any number of moves, words[i] == words[j].

For example, words[i] = "zzxy" and words[j] = "xyzz" are special-equivalent because we may make the moves "zzxy" -> "xzzy" -> "xyzz".

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

Every pair of strings in the group are special equivalent, and
The group is the largest size possible (i.e., there is not a string words[i] not in the group such that words[i] is special-equivalent to every string in the group).

Return the number of groups of special-equivalent strings from words.

Examples

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.
The other two groups are ["xyzz", "zzxy"] and ["zzyx"].
Note that in particular, "zzxy" is not special equivalent to "zzyx".

Input: words = ["abc","acb","bac","bca","cab","cba"]
Output: 3

Constraints

1 <= words.length <= 1000
1 <= words[i].length <= 20
words[i] consist of lowercase English letters.
All the strings are of the same length.

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n * l log l)
    # Space: O(n * l)
    def num_special_equivalent_groups(self, words: list[str]) -> int:
        signatures = {("".join(sorted(word[0::2])), "".join(sorted(word[1::2]))) for word in words}
        return len(signatures)

Complexity

Time	Space
O(n * l log l)	O(n * l)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Groups of Special-Equivalent Strings

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags