По заданной строке найдите длину самой длинной подстроки в ней, не превышающей K различных символов.
Пример:
Input: String = "araaci", K = 2 Вывод: 4 Объяснение: Самая длинная подстрока, содержащая не более 2 символов, является «araa».
Вход: String = «araaci», K = 1 Выход: 2 Объяснение: Самая длинная подстрока с не более '1' различных символов - это "aa".
Входные данные: String = "cbbebi", K = 3 Выходные данные: 5 Объяснение: Самые длинные подстроки с не более чем 3-мя различными символами являются "cbbeb" "&>" bbebi ".
Я получил решение, пройденное тестовыми примерами, как приведенные выше примеры, и я думаю, что это довольно оптимизированная скорость O (n) и пространство O (1). Но когда я пытаюсь go повторить это, я не могу понять, почему почему это работает ...
Может кто-нибудь помочь мне понять это? очень ценится.
def longest_substring_with_k_distinct(str, k):
seen = set()
max_, start = 0, 0
for end in range(len(str)):
seen.add(str[end])
max_ = max(end-start, max_)
while len(seen)>k:
if str[start] in seen:
seen.remove(str[start])
start+=1
return max_
Обновление : приведенный выше код неправильный , так как он работает только для тестовых случаев в примере, если мы настроим сначала пример 'aciara', затем код не будет работать. Следующий код будет правильным sol:
def longest_substring_with_k_distinct(str, k):
# TODO: Write your code here
if not str:
return 0
start, max_ = 0, 0
seen = set()
for end in range(len(str)):
seen.add(str[end])
while len(seen)>k:
if str[start] in seen:
seen.remove(str[start])
start+=1
max_ = max(max_, end-start+1)
return max_