Так как в этой задаче баланс между операциями записи и чтения смещен в сторону записи, нам необходимо минимизировать операции по модификации исходного массива. В данном случае нам на помощь может прийти сортировка и бинарный поиск:
— В отсортированном массиве подсказки для каждого префикса будут идти друг за другом, поэтому задача сведется к поиску первого элемента в массиве по префиксу и последующей проверки двух следующих элементов,
— С поиском первого элемента в отсортированном массиве хорошо справится бинарный поиск


➡️ Оптимальное решение

#medium #trie #binary_search