Leetcode 893. Groups of Special-Equivalent Strings

Problem Explanation

We are given an array of strings and asked to figure out groups of special-equivalent strings. Two strings are said to be special-equivalent if after any number of moves, one string can be transformed to another. A move in this case refers to swapping of elements at index i and index j such that both indices have the same parity (i % 2 == j % 2).

The function should return the number of these groups. A group is a non-empty subset of string where any string not in the subset isn't special-equivalent with any string in the subset.

Walk through an example.

Let's say the input is ["aa","bb","ab","ba"]. Here each string can be a group on its own since none of the strings can be transformed to another through a sequence of moves. Therefore, the function will return 4.

Approach of the solution.

Here, the algorithm used can be broken down into the following steps:

1. Initialize an empty set. This set will keep track of special-equivalent string groups.
2. Iterate through each string in the array.
3. For each string, split it into 2 separate strings "even" and "odd", where "even" contains characters from even-indexed positions, and "odd" contains characters from odd-indexed positions.
4. Sort both the "even" and "odd" strings. We sort them because swapping can give us a sorted string.
5. Concatenate "even" and "odd" strings and add the result into the set.
6. Finally, return the size of the set since the set keeps track of the special-equivalent string groups.

Python

1
2python
3from collections import Counter
4class Solution:
5  def numSpecialEquivGroups(self, words):
6    set = Counter([''.join(sorted(word[0::2]) + sorted(word[1::2])) for word in words])
7    return len(set)
8

Java

1
2java
3import java.util.*;
4class Solution {
5    public int numSpecialEquivGroups(String[] words) {
6        Set<String> set = new HashSet<>();
7        for (String word : words) {
8            int[] even = new int[26];
9            int[] odd = new int[26];
10            for (int i = 0; i < word.length(); i++) {
11                if (i % 2 == 1) odd[word.charAt(i) - 'a']++;
12                else even[word.charAt(i) - 'a']++;
13            }
14            String s = Arrays.toString(even) + Arrays.toString(odd);
15            set.add(s);
16        }
17        return set.size();
18    }
19}

JavaScript

1
2javascript
3var numSpecialEquivGroups = function(words) {
4  var set = new Set();
5  words.forEach(word => {
6    let even = '', odd = '';
7    for (let i = 0; i < word.length; i++) {
8        if (i % 2 === 0) {
9            even += word[i];
10        } else {
11            odd += word[i];
12        }
13    }
14    even = even.split('').sort().join('');
15    odd = odd.split('').sort().join('');
16    set.add(even + odd);
17  });
18  return set.size;
19};

C++

1
2c++
3#include <unordered_set>
4#include <vector>
5#include <string>
6class Solution {
7 public:
8  int numSpecialEquivGroups(vector<string>& words) {
9    unordered_set<string> set;
10    for (const string& word : words) {
11        string even;
12        string odd;
13        for (int i = 0; i < word.length(); ++i)
14            if (i % 2 == 0)
15                even += word[i];
16            else
17                odd += word[i];
18        sort(begin(even), end(even));
19        sort(begin(odd), end(odd));
20        set.insert(even + odd);
21    }
22    return set.size();
23  }
24};

C#

1
2csharp
3public class Solution {
4  public int NumSpecialEquivGroups(string[] words) {
5    var set = new HashSet<string>();
6    foreach (var word in words) {
7        var even = new List<char>();
8        var odd = new List<char>();
9        for (int i = 0; i < word.Length; i++)
10            if (i % 2 == 0) even.Add(word[i]);
11            else odd.Add(word[i]);
12        even.Sort();
13        odd.Sort();
14        var key = new string(even.ToArray()) + new string(odd.ToArray());
15        set.Add(key);
16    }
17    return set.Count;
18  }
19}

These solutions demonstrate the general approach to solving this problem in several different programming languages: namely, separating the characters in each string based on their index parity, sorting the separated characters, and then checking how many unique combinations of the sorted characters exist.

These solutions have a time complexity of O(nmlog(m)), where n is the number of strings in the given array, and m is the length of the longest string. The space complexity also depends on these two values, and in the worst-case scenario, it is also O(n*m).

It's worth noting some of the language-specific aspects of these solutions. For example, in Python, a built-in function Counter is used to count the occurrences of each string, while Java uses Arrays.toString() to convert arrays to strings for comparison.

In JavaScript, the Set object lets you store unique values of any type and provides various operations like adding a value, checking if a value exists, and obtaining the number of stored values.

C++ and C# implementations takes similar approach by manually sorting the characters, where C++ uses functionalities provided by STL(sort(), begin(), end()). On the other hand, C# uses List<> to store characters and sort them.

In essence, though the syntax varies across these languages, the conceptual approach remains the same. With a good understanding of your chosen language's syntax and built-in tools, you can employ this method to efficiently solve the problem of finding special-equivalent strings in an array.