Algorithm
Problem Name: 893. Groups of Special-Equivalent Strings
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"andwords[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 thatwords[i]is special-equivalent to every string in the group).
Return the number of groups of special-equivalent strings from words.
Example 1:
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".
Example 2:
Input: words = ["abc","acb","bac","bca","cab","cba"] Output: 3
Constraints:
1 <= words.length <= 10001 <= words[i].length <= 20words[i]consist of lowercase English letters.- All the strings are of the same length.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const numSpecialEquivGroups = function(A) {
return new Set(
A.map(word =>
[...word]
.reduce((counter, c, i) => {
counter[c.charCodeAt(0) - "a".charCodeAt(0) + 26 * (i % 2)]++;
return counter;
}, new Array(52).fill(0))
.join("-")
)
).size;
};
Input
Output
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numSpecialEquivGroups(self, A):
return len(set("".join(sorted(s[0::2])) + "".join(sorted(s[1::2])) for s in A))
Input
Output
#3 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Text;
namespace LeetCode
{
public class _0893_GroupsOfSpecialEquivalentStrings
{
public int NumSpecialEquivGroups(string[] A)
{
var set = new HashSet < string>();
var odds = new char[(A[0].Length + 1) / 2];
var evens = new char[A[0].Length / 2];
var sb = new StringBuilder();
foreach (var str in A)
{
for (var i = 0; i < str.Length; i++)
{
if (i % 2 == 0) odds[i / 2] = str[i];
else evens[i / 2] = str[i];
}
Array.Sort(odds);
Array.Sort(evens);
sb.Clear();
sb.Append(odds);
sb.Append(evens);
set.Add(sb.ToString());
}
return set.Count;
}
}
}
Input
Output