Минимум замен до палиндрома

1. Идея

Палиндром — это строка, которая читается одинаково слева направо и справа налево.

Значит, для каждого символа слева должен совпадать симметричный ему символ справа. Если они уже равны, ничего делать не нужно. Если не равны, то достаточно одной замены: можно изменить левый символ в правый или правый в левый.

Поэтому задача сводится к подсчёту количества несовпадающих симметричных пар.

2. Наблюдения

1. Проверять нужно только пары позиций:

   • 0 и n - 1
   • 1 и n - 2
   • 2 и n - 3
   • и так далее

2. Если строка нечётной длины, центральный символ ни с чем не сравнивается и никогда не требует замены.

3. Для каждой несовпадающей пары нужен ровно один ход:

   • например, в строке ab символы различаются, и одной заменой можно получить aa или bb.

4. Разные пары не зависят друг от друга, поэтому ответ — это просто число таких несовпадений.

3. Алгоритм

Будем использовать два указателя:

• left — в начале строки
• right — в конце строки

Пока left < right:

1. сравниваем s[left] и s[right]
2. если они различаются, увеличиваем ответ на 1
3. сдвигаем left вправо, а right влево

Когда указатели встретились или пересеклись, все нужные пары проверены.

4. Почему это работает

Рассмотрим любую симметричную пару символов.

• Если символы одинаковые, эта пара уже подходит для палиндрома, менять ничего не надо.
• Если символы разные, то для выполнения условия палиндрома они должны стать одинаковыми. Это можно сделать одной заменой, и меньше чем одной заменой это сделать нельзя.

Значит:

• каждая несовпадающая пара обязательно добавляет 1 к ответу;
• каждая совпадающая пара добавляет 0.

Так как все пары независимы, минимальное число замен равно количеству несовпадающих симметричных пар.

Именно это и считает алгоритм.

5. Сложность

Пусть длина строки равна n.

• Время работы: O(n), потому что каждый символ участвует не более чем в одном сравнении.
• Память: O(1), если не считать хранение самой строки.

6. Код на C++17

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;

    int left = 0;
    int right = (int)s.size() - 1;
    int ans = 0;

    while (left < right) {
        if (s[left] != s[right]) {
            ans++;
        }
        left++;
        right--;
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

s = input()

left = 0
right = len(s) - 1
ans = 0

while left < right:
    if s[left] != s[right]:
        ans += 1
    left += 1
    right -= 1

print(ans)