Условие

Дана строка s. Определите, можно ли сделать её палиндромом, удалив не более одного символа.

Примеры

Input: s = "aba” Output: true

Input: s = "abca” Output: true Explanation: Удалив символ 'b' или 'c', строка становится палиндромом.

Input: s = "abc” Output: false

Решение

fun validPalindrome(s: String): Boolean {
    fun isPalindrome(low: Int, high: Int): Boolean {
        var i = low
        var j = high
        while (i < j) {
            if (s[i] != s[j]) return false // Если символы не равны, это не палиндром
            i++
            j--
        }
        return true
    }

    var left = 0
    var right = s.length - 1

    while (left < right) {
        if (s[left] != s[right]) {
            // Проверяем, станет ли строка палиндромом, если удалить символ слева или справа
            return isPalindrome(left + 1, right) || isPalindrome(left, right - 1)
        }
        left++
        right--
    }

    return true // Если проверка завершилась без удаления, строка уже палиндром
}

Временная сложность

O(n), где n — длина строки, так как каждая проверка требует линейного прохода.

Пространственная сложность

O(1), так как используется фиксированное количество переменных.