LeetCode: Groups of Special-Equivalent Strings

You are given an array A of strings.

A move onto S consists of swapping any two even indexed characters of S, or any two odd indexed characters of S.

Two strings S and T are special-equivalent if after any number of moves onto S, S == T.

For example, S = “zzxy” and T = “xyzz” are special-equivalent because we may make the moves “zzxy” -> “xzzy” -> “xyzz” that swap S[0] and S[2], then S[1] and S[3].

Example 1:

Input: ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3

Example 2:

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

Note:

1 <= A.length <= 1000
1 <= A[i].length <= 20
All A[i] have the same length.
All A[i** consist of only lowercase letters.

Straightforward Solution

Special equivalent means two string have the same char set on even and odd positions. So we compare all the pairs of array.

is_same use two arrays to store the chars count of strings.

Time complexity is O(N^2 * 26).

class Solution {
public:
    bool is_same(string A, string B) {
        vector<int> count_odd(26, 0);
        vector<int> count_eve(26, 0);
        for(int i=0; i<A.size(); i++) {
            if(i%2) count_odd[A[i]-'a']++;
            else count_eve[A[i]-'a']++;
        }
        for(int i=0; i<B.size(); i++) {
            if(i%2) count_odd[B[i]-'a']--;
            else count_eve[B[i]-'a']--;
        }
        for(int i=0; i<26; i++) {
            if(count_odd[i] || count_eve[i]) 
                return false;
        }
        return true;
    }
    int numSpecialEquivGroups(vector<string>& A) {
        int flag[A.size()];
        for(int i=0; i<A.size(); i++) 
            flag[i] = i;
        for(int i=0; i<A.size(); i++) {
            int x = flag[i];
            if(x != i) continue;
            for(int j=i+1; j < A.size(); j++) { 
                int y = flag[j];
                if(y != j) continue;
                if(is_same(A[x], A[y])) {
                    flag[y] = x;
                }
            }
        }
        set<int> s;
        for(int i=0; i<A.size(); i++) 
            s.insert(flag[i]);
        return s.size(); 
    }
};

Sort based on index and add to Set

Another simpler method to check whether two string is special equivalent is split a string into the odd part and even part, then sort two parts separately and combine into a new string.

Time complexity is O(N* M*log(M)), where M is the max length of string.

class Solution {
public:

    string convert(string str) {
        string odd;
        string even;
        for(int i=0; i<str.size(); i++)
            i%2 == 0 ? odd += str[i] : even += str[i];
        sort(odd.begin(), odd.end());
        sort(even.begin(), even.end());
        return even + odd;
    }
    int numSpecialEquivGroups(vector<string>& A) {
        set<string> S;
        for(int i=0; i<A.size(); i++)
            S.insert(convert(A[i]));
        
        return S.size();
    }
};

One line Python solution

str[::2] can filter all chars at even positions, and str[1::2] will filter all chars in odd positions.

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

Join my Email List for more insights, It's Free!😋

← LeetCode: Sort Array By Parity II LeetCode: Remove Duplicate Node ... →