Dana jest łańcuch S. Czy jest on prawie palindromem (palindromem po usunięciu nie więcej niż jednego znaku)?

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

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