Informática Intermediário - Semana 40

Palíndrome

Um palíndrome é uma string que caso inversa é igual a original.

Você deve escrever um programa que dado uma string, determine o número mínimo de inserções de letras na string, para que se obtenha uma palindrome.

Por exemplo, a string Ab3bd pode ser transformada num palíndrome dAb3bAd ou Adb3bdA. Porém inserir menos de 2 caracteres não forma um palíndrome.

Entrada

A primeira linha contém um inteiro n\ (1\leq n \leq 5000), o tamanho da string de entrada.

A segunda linha contém a string de tamanho n. A string será formada dos caracteres A-Z, a-z, 0-9.

Saída

A uníca linha deve conter um inteiro, o número mínimo desejado.

Exemplos

Entrada Saída
5

Ab3bd

2