Можно ли из строки сделать палиндром одной перестановкой
Есть строка из латинских букв. Необходимо определить, возможно ли из этой строки получить палиндром, поменяв не более двух символов местами(т.е. одна перестановка). Например если есть строка: abbac. Из неё одной перестановкой мы не можем получить палиндром. А из строки abacaba - можем. Попытался реализовать алгоритм, который последовательно проверяет пары(0 и 1, 1 и 2, 2 и 3) он меняет в них символы местами и если получает палиндром, то считаем, что возможно, иначе нет. Данный алгоритм работает не всегда корректно. Код:
s = input()
for i in range(0, len(s)):
tmp = f'{s[:i]}{s[i:i+2][::-1]}{s[i+2:]}'
if tmp == tmp[::-1]:
print(True)
exit()
print(False)
Ответы (1 шт):
Про перестановку не соседних букв вам правильно подсказали. При реализации этого замечания код будет работать, но не быстро, т.к. проверка всех пар занимает квадратичное время.
Однако задача может быть решена и за линейное время - проходим по строке, проверяя на совпадение символ из левой половинки и соответствующий символ правой половинки. При этом считаем количество несовпадающих пар, и записываем их позиции. Получили 3 пары - всё, аллес капут.
Если после проверки несовпадений 0, то строка уже палиндром, и, если обмен непременно нужен, можно обменять любую пару, так что этот случай даёт True
Если несовпадений 2, то проверяем, можно ли обменять один из элементов первой пары с одним из элементов второй пары, чтобы получилось хорошо. По сути, пары при упорядочивании должны быть одинаковыми (или приведение ко множеству, или просто сравнения можно использовать)
Если несовпадение только одно, то для нечётной длины проверяем, можно ли средний элемент поменять с одним из пары (т.е. он равен другому из пары), для чётной длины, насколько я понимаю, решения нет
a b c b c a
1 2 2 1 номер пары несовпадающей, пары при упорядочивании равные, так что True
a b b c a
1 ^ 1
| средний элемент равен одному из пары