Dada una cadena S. ¿Es casi un palíndromo (un palíndromo después de eliminar no más de un carácter)?

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

Пример на 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 — длина строки.