Задача с собеседования в Яндекс

Дан массив строк strs. Найдите анаграммы и сгруппируйте их вместе.
Группы анаграмм можно вывести в любом порядке.

Пример:
Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Чат алгоритмистов

Решение
Идея: хэш-таблица, где ключ - кортеж из 26 эл-ов (каждое число - количество вхождений определённой буквы в слово), а значение - список слов, имеющих одинаковую частоту букв (анаграммы).
Проходим по каждому слову в массиве strs и создаём массив из 26 нулей (кол-во букв алфавита). Для каждого символа в слове вычисляем его индекс (соответствует позиции буквы в алфавите) и увеличиваем счётчик.
Далее преобразовываем список в кортеж, чтобы сделать его ключом словаря.
Проверяем, есть ли ключ в словаре. Если да: добавляем слово в существующий список анаграмм по этому ключу, если нет: создаём новую группу анаграмм.
Выводим двумерный список, состоящий из сгруппированных значений нашего словаря с анаграммами.

Сложность
O(n × k) - по времени
O(n × k) - по памяти

Код

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagrams = {}

for word in strs:
letter_counts = [0] * 26

for char in word:
letter_counts[ord(char) - ord("a")] += 1

key = tuple(letter_counts)

if key not in anagrams:
anagrams[key] = [word]
else:
anagrams[key].append(word)

return list(anagrams.values())

@algoses