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 larga de S que contenga máximo 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áximo número de caracteres diferentes permitidos en la substring.La salida debe tener exactamente una línea con un entero: la longitud de la substring más larga de S que tenga K ó menos caracteres diferentes.
codeo
3
4
K = 3, entonces nuestra substring puede tener máximo 3 letras diferentes.
No podemos agarrar la
string completa porque tiene 4 letras diferentes, y 4 > K. Tampoco podemos agarrar la substring "code" porque también tiene 4 letras diferentes.
La solución es la substring "odeo" que tiene 3 letras diferentes
y longitud 4. La substring "cod" también sería válida, pero es más corta que "odeo".
abaca
2
3
Hay dos posibles soluciones: "aba" ó "aca", ambas con longitud 3.
aaaaa
1
5
Cuando todas las letras son iguales la mejor solución siempre es agarrar toda la string.
abbbbcccddee
3
9
La solución es "bbbbcccdd" que tiene 3 letras diferentes y longitud 9. Todas las demás substrings que tienen máximo 3 letras diferentes, como "abbbbccc" ó "cccddee", son más cortas.
interesante
26
11
Cuando K es 26 nuestra substring puede tener cualquier letra porque sólo
existen 26 letras en el alfabeto, entonces la solución siempre es agarrar la
string completa.
1 ≤ |S| ≤ 100 y 1 ≤ K ≤ 26.1 ≤ |S| ≤ 100,000 y 1 ≤ K ≤ 26.