Задача: 893. Groups of Special-Equivalent Strings
Сложность: medium

Вам дан массив строк одинаковой длины words. За один ход вы можете поменять местами любые два четных или любые два нечетных символа строки words[i]. Две строки words[i] и words[j] являются специально-эквивалентными, если после любого количества ходов words[i] == words[j].

Например, words[i] = "zzxy" и words[j] = "xyzz" являются специально-эквивалентными, потому что мы можем делать ходы "zzxy" -> "xzzy" -> "xyzz". Группа специально-эквивалентных строк из слов - это непустое подмножество слов, такое, что: каждая пара строк в группе специально-эквивалентна, и группа имеет максимально возможный размер (т.е, не существует строки words[i], не входящей в группу, такой, что words[i] является специально-эквивалентной каждой строке в группе). Верните количество групп специально-эквивалентных строк из слов.

Пример:

Input: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3

👨‍💻 Алгоритм:

1⃣Для каждой строки в массиве words создать два новых списка: один из символов на четных позициях, другой из символов на нечетных позициях. Отсортировать оба списка и объединить их в одну строку, которая будет представлять каноническую форму строки.

2⃣Использовать множество, чтобы хранить все уникальные канонические формы строк.

3⃣Размер множества будет равен количеству групп специально-эквивалентных строк.

😎 Решение:

fun numSpecialEquivGroups(words: Array<String>): Int {
    val uniqueForms = mutableSetOf<String>()
    
    for (word in words) {
        val evenChars = word.filterIndexed { index, _ -> index % 2 == 0 }.toCharArray().sorted()
        val oddChars = word.filterIndexed { index, _ -> index % 2 != 0 }.toCharArray().sorted()
        val canonicalForm = evenChars.joinToString("") + oddChars.joinToString("")
        uniqueForms.add(canonicalForm)
    }
    
    return uniqueForms.size

Ставь 👍 и забирай 📚 Базу знаний