 Coder's Cat

## LeetCode: Groups of Special-Equivalent Strings

2020-11-30

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 and S, then S and S.

Example 1:

Example 2:

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).

## 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.

## One line Python solution

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

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