Задача с собеседования в Яндекс

На входе дана непустая строка. Требуется вяснить, можно ли удалить из нее ровно один символ так, чтобы получился палиндром.

Требуется решение за линейное время с константой дополнительной памяти.

наш чат алгоритмистов

Решение:
Несложно заметить следующее
Если строка уже является палиндромом, то ответ всегда положительный (достаточно удалить центральный или один из центральных символов)
В противном случае, если начать проверку строки на палиндромность с левого и правого концов - можно найти первое несовпадение abcX....Ycba. Можно заметить, что в случае положительного ответа на задачу один из символов X или Y в данном несовпадении должен быть удален и что после этого палиндромом должна быть строка .....Y или X.....

Таким образом, решение задачи сводится к поиску такого несовпадения и проверки двух случаев

def can_be_palindrome_by_removing_one_char(s):
def is_palindrome_range(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True

left, right = 0, len(s) - 1
while left < right and s[left] == s[right]:
left += 1
right -= 1

if left >= right:
return True # строка уже палиндром или можно удалить любой символ

# Проверяем два варианта: пропустить символ слева или справа
return (is_palindrome_range(left + 1, right) or
is_palindrome_range(left, right - 1))

@algoses