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.
La entrada contiene exactamente 2 líneas:
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.K
, el mínimo número de caracteres diferentes que debe tener la substring.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.
codeo
3
3
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.
abaca
3
3
La substring más corta con 3 ó más letras diferentes es "bac"
.
aaaaa
2
-1
En este caso nos piden encontrar una substring con al menos 2 letras diferentes, pero esto es imposible porque todas las letras son iguales.
abbbbcccddee
3
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
).
interesante
1
1
Si la substring sólo necesita tener una letra diferente, la solución es agarrar cualquier substring de longitud 1.
abaaaaaac
3
8
La respuesta es "baaaaaac"
. Desafortunadamente tenemos que agarrar todas las aes del medio para poder tener 3 letras diferentes en total.
1 ≤ |S| ≤ 100
y 1 ≤ K ≤ 26
.1 ≤ |S| ≤ 100,000
y 1 ≤ K ≤ 26
.