Условие

Дана строка s, содержащая только символы 'a' и 'b'. За один шаг можно удалить любую палиндромную подпоследовательность из строки.

Верни минимальное количество шагов, чтобы удалить всю строку.

Примечание: Подпоследовательность — это строка, которую можно получить, удалив некоторые (возможно, ноль) символов без изменения порядка оставшихся. Палиндром — строка, читающаяся одинаково в обе стороны.

Примеры

Input: s = "ababa” Output: 1 Explanation: Вся строка — палиндром.

Input: s = "abb” Output: 2 Explanation: Сначала удалить "bb", затем "a".

Input: s = "baabb” Output: 2 Explanation: Например, удалить "bbbb", затем "aa".

Решение

fun removePalindromeSub(s: String): Int {
    // Если строка пустая — 0 шагов
    if (s.isEmpty()) return 0

    // Проверка, является ли строка палиндромом
    var left = 0
    var right = s.length - 1
    while (left < right) {
        if (s[left] != s[right]) {
            return 2 // Если не палиндром — потребуется максимум 2 шага
        }
        left++
        right--
    }

    return 1 // Если палиндром — удаляется за 1 шаг
}

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

O(n), где n — длина строки, на проверку палиндрома.

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

O(1) — используется постоянное количество памяти.