Вам дана бинарная строка s длины n, состоящая из нулей и единиц. Назовем строку w длины…
- User
Вам дана бинарная строка s длины n, состоящая из нулей и единиц. Назовем строку w длины m красивой, если существует позиция 1≤i<m−i+1 такая, что w_i=w_m−i+1. Ваша задача – удалить наименьшее количество символов из строки s чтобы получить красивую строку. Выведите это наименьшее количество или −1, если цель недостижима.
- Assistant
Для решения данной задачи нужно обработать строку так, чтобы количество удалённых символов для достижения красивой строки (если это возможно) было минимальным. Рассмотрим пошаговый подход к решению задачи.
Определение красивой строки
Строка длины ( m ) является красивой, если существует индекс ( i ) (( 1 \leq i < m - i + 1 )) такой, что: [ w[i] = w[m-i+1] ]
Проще говоря, существует хотя бы одна пара символов в строке, симметричная относительно её середины, и они совпадают.
Подход к решению
Наша цель — удалить минимальное количество символов из строки ( s ), чтобы строка ( w ), образованная из оставшихся символов, была красивой. Если это невозможно, выведите (-1).
-
Проверка тривиального случая:
Если ( n < 2 ), то автоматически выполнить условие невозможно, так как в строке недостаточно символов для проверки симметрии. В этом случае ответ (-1). -
Поиск минимальных удалений:
Оптимальный способ решения задачи — использовать два указателя (поиск на краях строки):- Левый указатель ( l ) начинает с позиции ( 0 ) (первый символ).
- Правый указатель ( r ) начинает с конца строки ( n-1 ) (последний символ).
Повторяем процесс:
- Если ( s[l] = s[r] ) и ( l \leq r ), то эти символы формируют потенциальную красивую симметрию. Смещаем оба указателя внутрь (( l += 1, r -= 1 )).
- Если ( s[l] \neq s[r] ), нужно удалить один из символов.
Проверяем, какая ситуация при удалении приводит к более длинной "почти красивой" строке (левой или правой части). Например:- Удаление символа с позиции ( l ): Рекурсивно проверяем строку от ( l+1 ) до ( r ).
- Удаление символа с позиции ( r ): Рекурсивно проверяем строку от ( l ) до ( r-1 ). Выбираем вариант с минимальным количеством удалений.
-
Остановка процесса:
- Если ( l ) больше или равен ( r ), проверяем, есть ли в оставшейся строке хотя бы одна пара ( i, m-i+1 ), где ( w[i] = w[m-i+1] ). Если таких пар нет, возвращаем (-1).
-
Оптимизация (динамическое программирование): Чтобы избежать повторной проверки одних и тех же подстрок, можно использовать мемоизацию: сохраняем результаты для рассматриваемых пар указателей ( (l, r) ).
Реализация
Ниже приведён код на Python, демонстрирующий описанный процесс:
def min_deletions_to_beautiful(s): def is_beautiful(sub): # Проверяем, является ли подстрока красивой m = len(sub) for i in range(m // 2): if sub[i] == sub[m - i - 1]: return True return False def solve(l, r): # Базовый случай: если подстрока не может быть красивой if l >= r: return -1 # Если подстрока уже красивая if is_beautiful(s[l:r+1]): return 0 # Пробуем удалить символ справа или слева remove_left = solve(l + 1, r) remove_right = solve(l, r - 1) # Если ни одно удаление не приводит к успеху if remove_left == -1 and remove_right == -1: return -1 # Возвращаем минимальное количество удалений return 1 + min( remove_left if remove_left != -1 else float('inf'), remove_right if remove_right != -1 else float('inf') ) # Запускаем решение для всей строки n = len(s) if n < 2: return -1 # Невозможно сделать строку красивой result = solve(0, n - 1) return result if result != float('inf') else -1
Примеры
Пример 1:
Вход:
s = "0101"
Решение:
Строка уже является красивой, так как ( s[1] = s[4] ).
Ответ: ( 0 )Пример 2:
Вход:
s = "100"
Решение:
Удаляем ( s[2] ), чтобы получить строку "10", которая является красивой.
Ответ: ( 1 )Пример 3:
Вход:
s = "1"
Решение:
Невозможно сделать строку красивой (меньше двух символов).
Ответ: ( -1 )
Таким образом, используя описанный подход, можно найти минимальное количество удалений для превращения строки в красивую, либо определить, что это невозможно.
-