Решение задачи

Алгоритм решения задачи:

Чтобы проверить, является ли t перестановкой s, мы можем подсчитать количество вхождений каждой буквы в двух строках и сравнить их. Мы могли бы использовать хэш-таблицу для подсчета частоты каждой буквы, однако, поскольку и s, и t содержат только буквы от a до z, будет достаточно простого массива размером 26.

Нужны ли нам два счетчика для сравнения? На самом деле нет, потому что мы можем увеличивать счетчик для каждой буквы в ss и уменьшать счетчик для каждой буквы в tt, а затем проверять, равен ли счетчик для каждого символа нулю.

Временная сложность: O(n), так как потому что доступ к таблице счетчиков — это операция с постоянным временем.

Пространственная сложность: O(1). Хотя мы используем дополнительное пространство, сложность пространства составляет O(1), потому что размер таблицы остается постоянным независимо от того, насколько велико n.