Задача про палиндром

[Maxim19]

Здравствуйте, не знаю, можно ли такие задачи кидать на этом форуме, но вроде как вполне сходит на дискретную математику. Задача такова: Палиндромом называется строка, которая одинаково читается слева направо и справа налево. Рассмотрим некоторую строку $S$, состоящую из маленьких латинских букв. Какое минимальное количество букв (возможно нуль) нужно в ней удалить, чтобы она не являлась палиндромом? Предложите алгоритм решения задачи, докажите его корректность, оцените трудоемкость. Трудоёмкость состоит в O(n). Просто сравниваем с двух концов и ближе к центру, и ищем не равные символы. Мой вопрос в том, чтобы узнать, в чём сложность этой задачи? Если у кого то есть опыт в таких задачах, то расскажите, может я слишком плохой способ дал?

[mihaild]

Задача нормальная, ваше решение непонятно. Нам же нужно не проверить, является ли строка палиндромом, а удалить из неё что-нибудь, чтобы перестала являться.

[Maxim19]

Верно, любой палиндром можно сделать не таковым либо за либо 1 убирание, либо вообще нельзя(где все одинаковые)

-- 28.12.2022, 00:52 --

А вот это одно убирание, если идущие друг за другом символы не равны. И вот за O(n) проверяем эту штуку. Правда для начала так же за O(n) проверим, палиндром ли это вообще, сравнивая с двух концов символы.

[Mihaylo]

Надо найти минимальное число удалений и доказать корректность алгоритма.

Может надо не с конца, а из середины палиндрома начать?

[Andrey A]

Mihaylo в сообщении #1575292 писал(а):

... из середины палиндрома начать?

Из середины как раз максимальное количество имеем, поскольку без центрального знака (на оси симметрии или по соседству) палиндром остается палиндромом: $aba \rightarrow aa;\ \ abba \rightarrow aba.$

Maxim19 в сообщении #1575277 писал(а):

... либо вообще нельзя(где все одинаковые)

В числах — репьюниты. Вот если их исключить, то одного удаленного крайнего знака достаточно. Для доказательства надо разделить палиндромы на четные (по количеству знаков) и нечетные. В центре нечетного п. репьюнит из нечетного кол-ва знаков, как минимум из одного. В центре четного п. репьюнит из четного кол-ва знаков, как минимум из двух. При удалении крайнего знака четность меняется, а репьюнит в центре симметрии остается прежним: $aba \rightarrow ab;\ \ abba \rightarrow abb.$

[Mihaylo]

Andrey A в сообщении #1575297 писал(а):

Из середины как раз максимальное количество имеем

Вы не поняли. Находим середину палиндрома в строке, двигаясь от середины строки.
Возможно доказательством корректности будет доказательство того, более удаленные от середины строки серединки палиндрома будут менее оптимальными.
(Не путать середину строки с серединой палиндрома. В общем случае это не одно и то же.)

[Andrey A]

Maxim19 в сообщении #1575269 писал(а):

Рассмотрим некоторую строку $S$ , состоящую из маленьких латинских букв. Какое минимальное количество букв (возможно нуль) нужно в ней удалить, чтобы она не являлась палиндромом?

Я и теперь не понимаю. Вчитайтесь в свой вопрос, именно на него я и ответил. Если бы было написано "Какое минимальное количество букв (возможно нуль) нужно в ней удалить, чтобы она не содержала ни одного палиндрома?" — это был бы, конечно, другой вопрос.

P.S. Возможно, имелось в виду удалить знаки без предварительного анализа, но тайно или явно анализировать все равно придется, или же надо удалять все знаки. Самое простое — тест на палиндром. При отрицательном результате удалять не нужно ничего, в противном случае — то что я написал.

[Mihaylo]

Упс. Перепутал два варианта: "чтобы не являлась палиндромом" и "чтобы являлась палиндромом".
Я второй вариант рассматривал, и он более интересный.
Первый вариант банален. Пользуемся определением палиндрома: просто проверяем на палиндромность и в зависимости от этого изменяем 0 или 1 символ.