Groups of Special-Equivalent Strings — Editorial

Opening the reading…

Intuitionwhy position parity determines the entire group

A move can swap characters only with other characters at positions of the same parity. Therefore, characters from even positions can move among even positions, and characters from odd positions can move among odd positions, but no character can cross from one group to the other.

Because any two positions inside one parity group can be swapped, the order within that group does not matter. A string is completely described by the multiset of its even-indexed characters and the multiset of its odd-indexed characters. Sorting both groups gives one canonical representation for every special-equivalence group: equivalent strings produce the same representation, while different representations cannot be transformed into one another.

Approachturn each string into a hashable identity

Create an empty hash set of canonical representations, because each distinct representation should contribute exactly one group.

For each word, collect characters at indices 0, 2, 4 and so on into an even string, because these characters can only be rearranged among themselves.

Collect characters at indices 1, 3, 5 and so on into an odd string, because odd positions form a separate rearrangement group.

Sort both strings, because sorting removes the original order while preserving exactly the multiset of characters available at each parity.

Concatenate the sorted even and odd strings and insert the result into the hash set; the two parts have fixed lengths because every input word has the same length, so this representation is unambiguous.

Return the size of the set, because one stored canonical representation corresponds to one maximal special-equivalence group.

Complexityn is the number of words and L is their common length

MEASURE	BOUND	WHY
Time	O(n x L log L)	Each word is scanned once, then its even and odd parts are sorted. Their total length is L, and sorting them costs at most O(L log L); repeating this for n words gives the bound. Hash insertion is O(L) on average for the representation.
Space	O(n x L) extra	The hash set can retain up to n different representations, each of length L, so the worst case is O(n x L) when every word belongs to a different group. The temporary even and odd strings use O(L), which is dominated by the set. The returned integer uses no output storage that needs to be counted.

Here n is the number of words and L is the common length of every word.

Annotated solutionC++ · sorting canonical forms · the direct hashing solution

CPPBuild the sorted even and odd signatures, then count distinct signatures with a hash set.

#include <algorithm>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
    int numSpecialEquivGroups(vector<string>& words) {
        unordered_set<string> seen;

        for (const string& word : words) {
            string even;
            string odd;

            for (int i = 0; i < static_cast<int>(word.size()); ++i) {
                if (i % 2 == 0) {
                    even += word[i];
                } else {
                    odd += word[i];
                }
            }

            sort(even.begin(), even.end());
            sort(odd.begin(), odd.end());
            seen.insert(even + odd);
        }

        return static_cast<int>(seen.size());
    }
};

The important placement is the split before sorting. Sorting the complete word would allow characters from even positions to appear interchangeable with characters from odd positions, which is not a legal move. Sorting the two parts independently preserves exactly the movements the problem permits.

The frequency-signature alternativea small optimisation when the alphabet is fixed

Instead of sorting each parity group, you can count how many times each lowercase letter appears at even and odd positions. There are only 26 possible letters, so building a signature takes O(L + 26) time rather than sorting. This is a genuine optimisation for a fixed alphabet, although the sorted representation is shorter and usually easier to verify.

CPPUse fixed-size frequency arrays to create a parity-aware signature without sorting.

#include <array>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
    int numSpecialEquivGroups(vector<string>& words) {
        unordered_set<string> seen;

        for (const string& word : words) {
            array<int, 26> even{};
            array<int, 26> odd{};

            for (int i = 0; i < static_cast<int>(word.size()); ++i) {
                if (i % 2 == 0) {
                    ++even[word[i] - 'a'];
                } else {
                    ++odd[word[i] - 'a'];
                }
            }

            string key;
            for (int count : even) {
                key += to_string(count) + ',';
            }
            key += '|';
            for (int count : odd) {
                key += to_string(count) + ',';
            }

            seen.insert(key);
        }

        return static_cast<int>(seen.size());
    }
};