Problem statement

https://leetcode.com/problems/groups-of-special-equivalent-strings/

Solution

Notice, that for each string what is matter is Counter for elements in odd places and Counter for elements in even places - we call this representative of string. However we can not easily compare counters, so we can create sorted string from even elements, then put sorted string from odd elements and check how many different strings we have in the end.

Complexity

Time complexity will be O(m log m n), where m is length of strings and n is number of strings, space is O(mn)

Code

class Solution:
    def numSpecialEquivGroups(self, A):
        return len({"".join(sorted(s[::2]) + sorted(s[1::2])) for s in A})

Remark

There is alternative way, where we keep counters for whole alphabet: then for each word we need to keep 26 + 26 elements, put them into tuple and compare in the end. Time complexity will be O(mn + An), where A is the length of alphabet.