Groups of Special-Equivalent Strings

Problem

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 ofgroups of special-equivalent strings from _words.

Examples

Example 1

1
2
3
4
5
6


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

1
2


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.

Solution

Method 1 – Canonical Form with Sorting

Intuition

Two strings are special-equivalent if, after any number of swaps of even or odd indexed characters, their even and odd indexed characters can be rearranged independently. Thus, the canonical form is obtained by sorting the even and odd indexed characters separately.

Approach

For each word, split its characters into even and odd indexed lists.
Sort both lists and concatenate them to form a canonical key.
Use a set to collect all unique canonical keys.
The answer is the size of the set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
    int numSpecialEquivGroups(vector<string>& words) {
        set<string> s;
        for (auto& w : words) {
            string even, odd;
            for (int i = 0; i < w.size(); ++i) {
                if (i % 2 == 0) even += w[i];
                else odd += w[i];
            }
            sort(even.begin(), even.end());
            sort(odd.begin(), odd.end());
            s.insert(even + odd);
        }
        return s.size();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func numSpecialEquivGroups(words []string) int {
    s := map[string]bool{}
    for _, w := range words {
        even, odd := []byte{}, []byte{}
        for i := 0; i < len(w); i++ {
            if i%2 == 0 {
                even = append(even, w[i])
            } else {
                odd = append(odd, w[i])
            }
        }
        sort.Slice(even, func(i, j int) bool { return even[i] < even[j] })
        sort.Slice(odd, func(i, j int) bool { return odd[i] < odd[j] })
        key := string(even) + string(odd)
        s[key] = true
    }
    return len(s)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    public int numSpecialEquivGroups(String[] words) {
        Set<String> s = new HashSet<>();
        for (String w : words) {
            StringBuilder even = new StringBuilder(), odd = new StringBuilder();
            for (int i = 0; i < w.length(); i++) {
                if (i % 2 == 0) even.append(w.charAt(i));
                else odd.append(w.charAt(i));
            }
            char[] e = even.toString().toCharArray(), o = odd.toString().toCharArray();
            Arrays.sort(e);
            Arrays.sort(o);
            s.add(new String(e) + new String(o));
        }
        return s.size();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
    fun numSpecialEquivGroups(words: Array<String>): Int {
        val s = mutableSetOf<String>()
        for (w in words) {
            val even = mutableListOf<Char>()
            val odd = mutableListOf<Char>()
            for (i in w.indices) {
                if (i % 2 == 0) even.add(w[i]) else odd.add(w[i])
            }
            s.add(even.sorted().joinToString("") + odd.sorted().joinToString(""))
        }
        return s.size
    }
}

1
2
3
4
5
6
7
8


class Solution:
    def numSpecialEquivGroups(self, words: list[str]) -> int:
        s = set()
        for w in words:
            even = sorted(w[::2])
            odd = sorted(w[1::2])
            s.add((''.join(even), ''.join(odd)))
        return len(s)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


use std::collections::HashSet;
impl Solution {
    pub fn num_special_equiv_groups(words: Vec<String>) -> i32 {
        let mut s = HashSet::new();
        for w in words {
            let (mut even, mut odd) = (Vec::new(), Vec::new());
            for (i, c) in w.chars().enumerate() {
                if i % 2 == 0 { even.push(c); } else { odd.push(c); }
            }
            even.sort_unstable();
            odd.sort_unstable();
            s.insert((even, odd));
        }
        s.len() as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
    numSpecialEquivGroups(words: string[]): number {
        const s = new Set<string>();
        for (const w of words) {
            const even: string[] = [], odd: string[] = [];
            for (let i = 0; i < w.length; i++) {
                if (i % 2 === 0) even.push(w[i]);
                else odd.push(w[i]);
            }
            even.sort();
            odd.sort();
            s.add(even.join('') + odd.join(''));
        }
        return s.size;
    }
}

Complexity

⏰ Time complexity: O(n * k log k) — For n words of length k, sorting dominates.
🧺 Space complexity: O(n * k) — For storing canonical forms in the set.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Canonical Form with Sorting#

Intuition#

Approach#

Code#

Complexity#