█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 4173

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

  • Autor: Serivt
  • Fecha: 2021-05-24 19:36:52 UTC (Hace casi 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.027 s 3 KBi
#2
Correcto
0.03 s 3 KBi
#3
Correcto
0.021 s 3 KBi
#4
Correcto
0.019 s 3 KBi
#5
Correcto
0.016 s 3 KBi
#6
Correcto
0.02 s 3 KBi
#7
Correcto
0.025 s 3 KBi
#8
Correcto
0.021 s 3 KBi
#9
Correcto
0.028 s 3 KBi
#10
Correcto
0.022 s 3 KBi
#11
Tiempo límite excedido
1.55 s 3 KBi
#12
Correcto
0.022 s 3 KBi
#13
Tiempo límite excedido
1.557 s 3 KBi
#14
Correcto
0.021 s 3 KBi
#15
Correcto
0.021 s 3 KBi
#16
Tiempo límite excedido
1.515 s 3 KBi
#17
Correcto
0.02 s 3 KBi
#18
Correcto
0.028 s 3 KBi
#19
Correcto
0.023 s 3 KBi
#20
Tiempo límite excedido
1.541 s 3 KBi
#21
Correcto
0.075 s 3 KBi
#22
Correcto
0.531 s 3 KBi
#23
Correcto
0.627 s 3 KBi
#24
Correcto
0.667 s 3 KBi
#25
Correcto
0.789 s 3 KBi
#26
Correcto
0.641 s 3 KBi
#27
Tiempo límite excedido
1.549 s 3 KBi
#28
Tiempo límite excedido
1.559 s 3 KBi
#29
Tiempo límite excedido
1.534 s 3 KBi
#30
Tiempo límite excedido
1.537 s 3 KBi
#31
Tiempo límite excedido
1.574 s 3 KBi
#32
Tiempo límite excedido
1.527 s 3 KBi
Puntos totales: 69 / 100

Código

import math

def find_min_substring(arr, k):
    distinct_chars = set()
    i, j = 0, 0
    answer = math.inf
    length = len(arr) 
    while j <= length:
        substring = arr[i:j]
        if len(set(substring)) >= k:
            i += 1
            answer = min(answer, len(substring))
            if answer == k:
                break
        else:
            j += 1
    return answer

s = input()
k = int(input())
min_substring = find_min_substring(s, k)
print(-1 if min_substring == math.inf else min_substring)