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

Envío 3458

Problema 0x59 - Substring más larga con máximo K caracteres diferentes

  • Autor: jocarmp08
  • Fecha: 2021-03-14 23:28:47 UTC (Hace alrededor de 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.023 s 3 KBi
#2
Correcto
0.03 s 3 KBi
#3
Correcto
0.032 s 3 KBi
#4
Correcto
0.024 s 3 KBi
#5
Correcto
0.031 s 3 KBi
#6
Correcto
0.044 s 6 KBi
#7
Correcto
0.024 s 3 KBi
#8
Correcto
0.026 s 3 KBi
#9
Correcto
0.033 s 3 KBi
#10
Correcto
0.136 s 3 KBi
#11
Correcto
0.129 s 3 KBi
#12
Correcto
0.088 s 3 KBi
#13
Correcto
0.139 s 3 KBi
#14
Correcto
0.09 s 3 KBi
#15
Correcto
0.157 s 3 KBi
#16
Correcto
0.137 s 3 KBi
#17
Correcto
0.138 s 3 KBi
#18
Correcto
0.146 s 3 KBi
#19
Correcto
0.03 s 3 KBi
#20
Correcto
0.13 s 3 KBi
#21
Correcto
0.15 s 3 KBi
#22
Correcto
0.13 s 3 KBi
#23
Correcto
0.027 s 3 KBi
#24
Correcto
0.113 s 3 KBi
Puntos totales: 100 / 100

Código

def longest_substring_k_distinct(s, k = 26):
    if k == 26:
        return len(s)
    
    longest_substring_size = 0
    window_start = 0
    char_freq = {}

    for window_end, current in enumerate(s):
        if current in char_freq:
            char_freq[current] = char_freq[current] + 1
        else: 
            char_freq[current] = 1

        while len(char_freq) > k:
            prev = s[window_start]

            if char_freq[prev] == 1:
                char_freq.pop(prev)
            else:
                char_freq[prev] = char_freq[prev] - 1

            window_start += 1

        longest_substring_size = max(longest_substring_size, window_end - window_start + 1)

    return longest_substring_size

s = input()
k = int(input())
        
print(longest_substring_k_distinct(s, k))