893. Groups of Special-Equivalent Strings LeetCode Solution
In this guide, you will get 893. Groups of Special-Equivalent Strings LeetCode Solution with the best time and space complexity. The solution to Groups of Special-Equivalent Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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” and words[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 that words[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”.
Input: words = [“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
Output: 3
Constraints:
1 <= words.length <= 1000
1 <= words[i].length <= 20
words[i] consist of lowercase English letters.
All the strings are of the same length.
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(n)
893. Groups of Special-Equivalent Strings LeetCode Solution in C++
class Solution {
public:
int numSpecialEquivGroups(vector<string>& words) {
unordered_set<string> set;
for (const string& word : words) {
string even;
string odd;
for (int i = 0; i < word.length(); ++i)
if (i % 2 == 0)
even += word[i];
else
odd += word[i];
ranges::sort(even);
ranges::sort(odd);
set.insert(even + odd);
}
return set.size();
}
}; /* code provided by PROGIEZ */
893. Groups of Special-Equivalent Strings LeetCode Solution in Java
class Solution {
public int numSpecialEquivGroups(String[] words) {
Set<String> set = new HashSet<>();
for (final String word : words) {
String even = "";
String odd = "";
for (int i = 0; i < word.length(); ++i)
if (i % 2 == 0)
even += word.charAt(i);
else
odd += word.charAt(i);
char[] evenCharArray = even.toCharArray();
char[] oddCharArray = odd.toCharArray();
Arrays.sort(evenCharArray);
Arrays.sort(oddCharArray);
set.add(new String(evenCharArray) + new String(oddCharArray));
}
return set.size();
}
} // code provided by PROGIEZ
893. Groups of Special-Equivalent Strings LeetCode Solution in Python
class Solution:
def numSpecialEquivGroups(self, words: list[str]) -> int:
return len({''.join(sorted(word[::2])) + ''.join(sorted(word[1::2]))
for word in words}) # code by PROGIEZ
