1642 - Teclado Quebrado

  • ID: 1642
  • IdBecrowd: 1642
  • Tags: programacao-dinamica, strings
  • Nível: 6
  • Tempo Limite: 2 segundos
  • Memória: 200 MB
  • Categoria: Paradigmas
  • Autor: Contest Local, Universidade de Ulm, Alemanha.

Descrição

O teclado do Bruce está quebrado, apenas algumas teclas ainda funcionam, Bruce descobriu que ele ainda pode digitar textos, mudando o layout do teclado, sempre que a letra necessária não está no mapeada para as m teclas que atualmente funcionam do teclado.

Dado o texto que Bruce deseja digitar, ele quer saber se você consegue dizer a ele o número máximo de caracteres consecutivos no texto, que pode ser digitado sem a necessidade de mudar o layout do teclado, Ou seja, cada tecla está mapeada para exatamente um carácter, e não é possível digitar esse carácter por outras combinações de teclas, isso significa que Bruce quer saber o comprimento da maior subsequência do texto, que consiste em no máximo m caracteres diferentes.

Entrada

A entrada consiste em vários casos de teste, cada caso de teste possui duas linhas. A primeira linha de cada caso contém o número m (1 ≤ m ≤ 128), que especifica o número de teclas restantes (as que ainda funcionam) . A segunda linha de cada caso de teste consiste no texto em que Bruce deseja digitar. Você pode deduzir que esse texto não ultrapasse 1 milhão de caracteres. Note que a entrada pode possuir caracteres de espaço, que devem ser tratados como qualquer outro carácter.

O último caso de teste é seguido por uma linha contendo um zero.

Dica: A maior substring para o primeiro caso de teste é “by_bru”, onde representa um caractere de espaço.

Saída

Para cada teste, imprima uma linha com o comprimento da maior subsequência do texto que consiste em no máximo m caracteres diferentes.

Exemplos

Exemplo de Entrada

5

This can't be solved by brute force.

1

Mississippi

0

Exemplo de Saída

7

2
Back to top