0xc9 - Substring más corta con mínimo K caracteres diferentes

Tenemos una string S.

Una substring de S es otra string formada por un bloque de caracteres consecutivos de S. Por ejemplo, algunas de las substrings de S = "codeo" son "c", "ode" y "codeo". Por otra parte, "cdeo" no es una substring de S porque no está formada por caracteres consecutivos de S.

Escribe un programa que lee una string y calcula la longitud de la substring más corta de S que contenga mínimo K caracteres diferentes.

Entrada

La entrada contiene exactamente 2 líneas:

• La primera línea tiene la string S. La string sólo tiene letras minúsculas entre a y z. No hay tildes, diéresis, espacios, eñes, números o signos de puntuación.
• La segunda línea contiene K, el mínimo número de caracteres diferentes que debe tener la substring.

Salida

La salida debe tener exactamente una línea con un entero: la longitud de la substring más corta de S que tenga K ó más caracteres diferentes.

Si no existe al menos una substring que tenga al menos K caracteres diferentes, la salida debe ser -1.

Entrada de ejemplo #1

codeo
3

Salida de ejemplo #1

3

Explicación del ejemplo #1

K = 3, entonces nuestra substring debe tener mínimo 3 letras diferentes.

Cualquiera de las substrings "cod", "ode" ó "deo" funcionan, y estas tienen longitud 3. La substring "odeo" también funciona pero es un poco más larga y queremos encontrar la más corta posible.

Entrada de ejemplo #2

abaca
3

Salida de ejemplo #2

3

Explicación del ejemplo #2

La substring más corta con 3 ó más letras diferentes es "bac".

Entrada de ejemplo #3

aaaaa
2

Salida de ejemplo #3

-1

Explicación del ejemplo #3

En este caso nos piden encontrar una substring con al menos 2 letras diferentes, pero esto es imposible porque todas las letras son iguales.

Entrada de ejemplo #4

abbbbcccddee
3

Salida de ejemplo #4

4

Explicación del ejemplo #4

En este caso K = 3, entonces queremos encontrar una substring que tenga 3 o más letras diferentes en total.

Algunas posibilidades son "abbbbccc" (que tiene tres letras diferentes: a, b y c), "cccddee" (que tiene tres letras diferentes: c, d y e) ó inclusive la string completa (que tiene 5 letras diferentes: a, b, c, d, y e).

Entre todas las posiblidades la más corta es "cdde", que tiene longitud 4 y también tiene 3 ≥ K letras diferentes (c, d y e).

Entrada de ejemplo #5

interesante
1

Salida de ejemplo #5

1

Explicación del ejemplo #5

Si la substring sólo necesita tener una letra diferente, la solución es agarrar cualquier substring de longitud 1.

Entrada de ejemplo #6

abaaaaaac
3

Salida de ejemplo #6

8

Explicación del ejemplo #6

La respuesta es "baaaaaac". Desafortunadamente tenemos que agarrar todas las aes del medio para poder tener 3 letras diferentes en total.

Restricciones

• En aproximadamente 30% de los puntos, está garantizado que 1 ≤ |S| ≤ 100 y 1 ≤ K ≤ 26.
• En el resto de los puntos, está garantizado que 1 ≤ |S| ≤ 100,000 y 1 ≤ K ≤ 26.

Envía tu solución