Groups Of Special Equivalent Strings - Leetcode Solution

Problem Statement:

Two strings A and B of lowercase letters are special-equivalent if after any number of moves, A == B.

A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].

Now, a group of special-equivalent strings from a given list S is a non-empty subset S1 of S such that any string not in S1 is not special-equivalent with any string in S1.

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

Solution:

To solve this problem, we need to find out the number of unique special-equivalent groups in the given list of strings A.

To do this, we can loop through each string in A, and find its special-equivalent version.

We can use a hash set to keep track of the special-equivalent groups we have seen so far.

For each string in A, we can generate all possible special-equivalent versions by swapping characters at even and odd indices.

Then, we can sort the resulting strings and add them to our hash set.

Finally, we return the size of our hash set, which gives us the number of unique special-equivalent groups.

Pseudo-code:

function numSpecialEquivGroups(A):

hash_set = set()

// Loop through each string in A
for s in A:
    
    // Generate all possible special-equivalent versions
    s_list = []
    even_chars = s[0::2]
    odd_chars = s[1::2]
    s_list.append(''.join(sorted(even_chars)) + ''.join(sorted(odd_chars)) )
    s_list.append(''.join(sorted(odd_chars)) + ''.join(sorted(even_chars)) )
    
    // Add special-equivalent versions to hash set
    for t in s_list:
        hash_set.add(t)

// Return size of hash set
return len(hash_set)

Time Complexity:

The time complexity of the above algorithm is O(NMlogM), where N is the number of strings in A and M is the maximum length of a string in A.

We need to loop through each string in A, and for each string, we need to generate two special-equivalent versions and sort them, which takes O(M*logM) time.

Since we perform this operation for each string in A, the total time complexity is O(NMlogM).

Space Complexity:

The space complexity of the above algorithm is O(NM), since we store two special-equivalent versions of each string in A in a list, which requires O(2M) space for each string. Since we perform this operation for each string in A, the total space complexity is O(N*M).

1