Дадена е низ S. Той е почти палиндром (палиндром след премахване на не повече от един символ)?

Чтобы проверить, является ли строка почти палиндромом (то есть палиндромом после удаления не более одного символа), можно использовать два указателя — с начала и с конца строки. Если символы не совпадают, пытаемся пропустить либо символ слева, либо справа, и проверить, образует ли оставшаяся подстрока палиндром.

Пример на Python:

def valid_palindrome(s: str) -> bool:
    def is_palindrome_range(i, j):
        return all(s[k] == s[j - k + i] for k in range(i, j))

    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            # Пропускаем либо левый, либо правый символ
            return is_palindrome_range(left + 1, right) or is_palindrome_range(left, right - 1)
        left += 1
        right -= 1
    return True

Этот алгоритм работает за O(n), где n — длина строки.