Gegeben ist eine Zeichenkette S. Ist sie fast ein Palindrom (ein Palindrom nach Entfernen von höchstens einem Zeichen)?

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

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