Задача «Подстрока»
Всем здравствуйте! Никак не могу решить следующую задачу.
«Подстрока»
Условие:
В этой задаче Вам требуется найти максимальную по длине подстроку данной строки такую, что каждый символ встречается в ней не более ? раз.
Входные данные:
В первой строке даны два целых числа ? и ? (1 ≤ ? ≤ 100000, 1 ≤ ? ≤ ?), где ? — количество символов в строке. Во второй строке ? символов — данная строка, состоящая только из строчных латинских букв.
Выходные данные:
В выходной файл выведите два числа — длину искомой подстроки и номер её первого символа. Если решений несколько, то выберите самую левую подходящую подстроку.
Примеры:
Ввод 1:
3 1
abb
Вывод 1:
2 1
Ввод 2:
5 2
ababa
Вывод 2:
4 1
Мой код:
n, k = map(int, input().split())
s = input()
d = dict().fromkeys(s, 0)
l = 0
for i in range(n):
sym = s[i]
if d[sym] <= k:
d[sym] += 1
else:
break
print(i - l, l + 1)
Тестирующая система выдаёт ошибку «Программа выдаёт неверный ответ». Подскажите, пожалуйста, в чём я совершил ошибку?
Ответы (2 шт):
Задача не сложная нужно
Вход K N Str
- Функция которая считает
kдля заданной строки.CountK(anystr) - Пробежаться по всем возможным подстрокам искомой строки и вычислять k для нее. Если
CountK(substr) <= K && len(substr) > lenKmaxтогда обновляем переменныеkMax, srtartIndex, LenKmax.
И к стати все подстроки получаются циклом для конца подстроки и циклом для начала подстроки.
Добавлю что не стоит бегать в сторону увеличения подстроки если k уже превысил ожидаемый. И понятно что не стоит искать подстроку в сторону уменьшения и вовсе имея уже на руках большую. Т.е двигаться по подстрокам уже имея при себе lenMax
Извиняюсь пишу с телефона. Завтра попробую написать код.
UPD
Подсчет countK
a = a[26] - массив счетчиков на каждый символ в строке
Понятно что CountK - это max(a) (максимальный из массива a); нахождение постоянно max(a) для каждой строки не много накладно, но можно это сделать по другому.
Ясно что при добавление одного символа в строку CountK будет равен CountK(string + char) = max(a[indexOf(char)]++, CountK(string))
и уменьшение строки на один символ
CountK(-char + string) = if (a[indexOf(char)] < CountK(string)) тогда это CountK(string) иначе уменьшаем a[indexOf(char)]-- и ищем max(a)
Делаем два индекса - левый и правый.
Двигаем правый, подсчитывая количество каждого символа на текущий момент в словарь со счётчиком.
Когда один из счётчиков становится больше k - останавливаемся, фиксируем длину как разницу правого и левого.
Двигаем левый индекс, уменьшая счётчики для каждого символа. Когда счётчик с превышением уменьшается - останавливаемся, и начинаем снова двигать правый индекс. И т.д.
from collections import Counter
s = 'abcaabaacacababca'
k = 2
left = 0
right = -1
n = len(s)
cntr = Counter()
maxlen = 0
maxleft = -1
while right < n:
while right < n:
right += 1
if right == n:
if right - left > maxlen:
maxlen = right - left
maxleft = left
break
ch = s[right]
cntr[ch] += 1
if cntr[ch]> k:
if right - left > maxlen:
maxlen = right - left
maxleft = left
break
while left < right:
ch = s[left]
left += 1
cntr[ch] -= 1
if cntr[ch] == k:
break
print(maxlen, maxleft)