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

😎 Решение:

import java.util.*;

class Solution {
    public int numSpecialEquivGroups(String[] words) {
        Set<String> uniqueForms = new HashSet<>();
        
        for (String word : words) {
            char[] evenChars = new char[(word.length() + 1) / 2];
            char[] oddChars = new char[word.length() / 2];
            
            for (int i = 0; i < word.length(); i++) {
                if (i % 2 == 0) {
                    evenChars[i / 2] = word.charAt(i);
                } else {
                    oddChars[i / 2] = word.charAt(i);
                }
            }
            
            Arrays.sort(evenChars);
            Arrays.sort(oddChars);
            String canonicalForm = new String(evenChars) + new String(oddChars);
            uniqueForms.add(canonicalForm);
        }
        
        return uniqueForms.size();
    }

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