Есть ли алгоритмы эффективнее сортировки для сравнения строк по составу символов

Что проверяют

Умеете ли вы оценить сложность и заменить сортировку подсчётом, когда алфавит ограничен. iOS-разработчику следом почти всегда задают вопрос про Unicode: что будет с кириллицей, эмодзи и заглавными буквами в вашем решении на Swift.

Как отвечать

Задача классическая: строки равны по составу, если они анаграммы друг друга.

• сортировка: a.sorted() == b.sorted(), O(n log n). Читается в одну строку и для коротких строк вполне годится;
• подсчёт частот: один проход по каждой строке, O(n) по времени и O(k) по памяти, где k размер алфавита. Для строчной латиницы хватает массива на 26 счётчиков: плюс для символов первой строки, минус для второй, в конце все нули;
• словарь: для произвольного текста [Character: Int], собранный через reduce(into: [:]) { $0[$1, default: 0] += 1 }, и сравнение двух словарей. Асимптотика та же, но константа выше из-за хеширования.

Здесь стоит показать знание Swift. String состоит из расширенных графемных кластеров, поэтому Character это видимый символ, а не байт, и сравнение идёт с учётом канонической эквивалентности: «é» одним кодом и «e» с комбинируемым акцентом равны. Подсчёт по utf8 быстрее, но это свойство теряет. count у строки вычисляется проходом, а не берётся готовым. Регистр приводят через lowercased() до подсчёта.

Если строк много и нужно сгруппировать анаграммы, ключом словаря делают либо отсортированную строку, либо массив счётчиков.

Где спотыкаются

Пишут char.asciiValue! - 97. На кириллице asciiValue равен nil, и приложение падает на force unwrap, а на заглавной латинице вычитание в UInt8 уходит в минус, и переполнение тоже роняет процесс.

Предлагают сравнивать сумму или произведение кодов символов. Сумма даёт коллизии, у «ad» и «bc» она одинакова, а произведение простых чисел на длинной строке быстро переполняется.

Утверждают, что O(n) всегда быстрее. На коротких строках сортировка маленького массива вполне может обогнать словарь с хешированием, и сильный ответ опирается на замер, а не только на асимптотику.