Задача: 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⃣Размер множества будет равен количеству групп специально-эквивалентных строк.

😎 Решение:

function numSpecialEquivGroups($words) {
    $uniqueForms = [];
    
    foreach ($words as $word) {
        $evenChars = [];
        $oddChars = [];
        
        for ($i = 0; $i < strlen($word); $i++) {
            if ($i % 2 == 0) {
                $evenChars[] = $word[$i];
            } else {
                $oddChars[] = $word[$i];
            }
        }
        
        sort($evenChars);
        sort($oddChars);
        $canonicalForm = implode('', $evenChars) . implode('', $oddChars);
        $uniqueForms[$canonicalForm] = true;
    }
    
    return count($uniqueForms);
}

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