Вопрос в следующем: напишите эффективный метод, который проверяет, является ли какая-либо перестановка ↴ входной строки палиндромом.
Подход грубой силы будет заключаться в проверке каждой перестановки входной строки, чтобы увидеть, является ли она палиндром.
Сколько будет времени? Для строки длины n их n! перестановки (n вариантов для первого символа, умноженное на n-1 выбор для второго символа, et c). Проверка каждой перестановки длины n, чтобы увидеть, является ли это палиндромом, включает проверку каждого символа, занимающую время O (n). Это дает нам в целом O (n! N) времени. Мы можем сделать лучше!
Как они достигли O (n! N)?