Матч 337, Палиндромизация 2 (Palindromize2)

Дивизион 2, Уровень 1

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

Класс: Palindromize2

Метод: string minChanges(string s)

Ограничения: services содержит от 1 до 50 строк длины не более 50 символов ‘A’-‘Z’,‘a’-‘z’, названия сервисов в каждой строке уникальны.

Вход. Строка s.

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

Пример входа

s

“ameba”

“cigartragic”

“abcdef”

Пример выхода

"abeba"

“cigartragic”

“abccba”

РЕШЕНИЕ

обработка строк

Двигаемся с начала и с конца строки к ее середине, просматривая буквы, стоящие на i - ом и len – i – 1 - ом месте (len – длина строки s, 0 £ i £ len / 2). Буквы, стоящие на этих местах, должны быть в палиндроме одинаковыми. Если они не равны между собой, делаем их равными той букве, которая имеет меньший ASCII код.

ПРОГРАММА

#include <cstdio>

#include <algorithm>

#include <string>

using namespace std;

class Palindromize2

{

public:

string minChanges(string s)

{

int i, len = s.size();

for(i = 0; i < len / 2; i++)

if (s[i] != s[len - i - 1])

s[i] = s[len - i - 1] = min(s[i],s[len - i - 1]);

return s;

}

};