Verilen bir S dizisi. Bu neredeyse bir palindrom mu (bir karakter çıkarıldıktan sonra palindrom mu)?

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

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