Блог

В вопросе говорится о преобразовании строки в палиндром путем замены символов в строке. Длина сформированной строки палиндрома должна быть такой же, как у исходной строки.

Например: строка abcde для преобразования в палиндром,

минимальное количество замен: 2

abcde -> abcba

А что, если для этого требуется, чтобы определенная подстрока была частью результирующей палиндромной строки?

Пример: строка требует, чтобы подстрока «tea» была частью результирующей строки

затем abcdef -> aettea

минимальная замена: 4

Палиндромы по определению одинаковы по обе стороны от их центральной точки.

Для строки с нечетными буквами максимальная длина строки минус один и деленная на два даст вам количество символов для замены.

 (length - 1) / 2 = #charsReplaced
 

Для строки с четной длиной максимальная длина заменяемых символов равна длине, деленной на два.

 length / 2 = #charsReplaced
 

Поиск минимального количества символов для замены потребовал бы чтения в строке каждым символом, сопоставления символов с каждой стороны центральной точки строки и определения того, какие из них похожи. Для каждого, у которого уже есть похожая буква на каждой стороне (например, у abcbe на 1 меньше максимального значения), вы отделяете это количество от максимального.

Это логическая проблема, но я думаю, вы можете вычислить ее, используя этот алгоритм, который я разработал:

пример: radaa
firsthalf: ra
проверяет обратную сторону другой половины:
совпадение aa, если равно: ra = aa
подсчитайте количество неравных символов: 1
замена: a = r
тогда вы получили свой результат: радар, ошибка 1 символа.