Palíndromo
Uma cadeia de caracteres é chamada de palíndromo se a sequência de caracteres da esquerda para a direita é igual à sequência de caracteres da direita para a esquerda (uma outra definição é que o primeiro caractere da cadeia deve ser igual ao último caractere da cadeia, o segundo caractere deve ser igual ao penúltimo caractere, o terceiro caractere deve ser igual ao antepenúltimo caractere, e assim por diante).
Por exemplo, as cadeias de caracteres ‘mim’, ‘axxa’ e ‘ananaganana’ são exemplos de palíndromos. Se uma cadeia não é palíndroma, ela pode ser dividida em cadeias menores que são palíndromas. Por exemplo, a cadeia ‘aaxyx’ pode ser dividida de quatro maneiras distintas, todas elas contendo apenas cadeias palíndromas: \‘aa’, ‘xyx’\, \‘aa’, ‘x’, ‘y’, ‘x’\, \‘a’, ‘a’, ‘xyx’\ e \‘a’, ‘a’, ‘x’, ‘y’, ‘x’\.
Dada uma cadeia de caracteres, escreva um programa que determine qual o menor número de partes em que a dada cadeia deve ser dividida de forma que todas as partes sejam palíndromos.
Entrada
A primeira linha contém um número inteiro N que indica o número de caracteres da cadeia. A segunda linha contém a cadeia de caracteres, composta por letras minúsculas, de ‘a’ a ‘z’, sem espaços em branco.Saída
Seu programa deve produzir uma única linha, contendo um número inteiro, o menor número de partes em que a cadeia de entrada deve ser dividida de forma que todas as partes sejam palíndromes.Restrições
- 1 ≤ N ≤ 2000
- A cadeia de caracteres contém apenas letras minúsculas não acentuadas (‘a’ a ‘z’).
Informações sobre a pontuação
- Em um conjunto de casos de teste somando 20 pontos, N ≤ 8
- Em um conjunto de casos de teste somando 40 pontos, N ≤ 300
Exemplos
Entrada
3 axa |
Saída
1 |
Entrada
6 xyzyyx |
Saída
4 |
Entrada
10 bbabcbbaab |
Saída
4 |
