3

Всем здравствуйте! Никак не могу решить следующую задачу.

«Подстрока»

Условие:

В этой задаче Вам требуется найти максимальную по длине подстроку данной строки такую, что каждый символ встречается в ней не более 𝑘 раз.

Входные данные:

В первой строке даны два целых числа 𝑛 и 𝑘 (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)

Тестирующая система выдаёт ошибку «Программа выдаёт неверный ответ». Подскажите, пожалуйста, в чём я совершил ошибку?

3
  • 2
    Искомая строка не обязана быть префиксом.
    – Qwertiy
    13 авг 2020 в 20:12
  • @Qwertiy, здравствуйте! Не совсем понятно, что Вы имеете ввиду. 13 авг 2020 в 20:53
  • 1
    @Daniil Savinov Вы решаете только для подстрок, которые начинаются с начала исходной строки (являются её префиксами)
    – MBo
    14 авг 2020 в 2:23

2 ответа 2

4

Делаем два индекса - левый и правый.

Двигаем правый, подсчитывая количество каждого символа на текущий момент в словарь со счётчиком.

Когда один из счётчиков становится больше 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)
16
  • А чем ответ отличается от моего? 14 авг 2020 в 5:09
  • 1
    @Aziz Umarov Тем, что он линейный, а не квадратичный. Он не проверяет все подстроки
    – MBo
    14 авг 2020 в 5:11
  • Добавлю что не стоит бегать в сторону увеличения подстроки если k уже превысил ожидаемый. и что если вы тоже сделаете все проверки что и я. Тогда у вас квадратичный или у меня линейный? 14 авг 2020 в 5:12
  • Как раз здесь алгоритм не бегает - становится больше k - останавливаемся
    – MBo
    14 авг 2020 в 5:13
  • 1
    Никакой из индексов у меня назад не возвращается, так что линейный.
    – MBo
    14 авг 2020 в 5:17
2

Задача не сложная нужно

Вход K N Str

  1. Функция которая считает k для заданной строки. CountK(anystr)
  2. Пробежаться по всем возможным подстрокам искомой строки и вычислять 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)

2
  • Не получится - во время не уложится.
    – Qwertiy
    13 авг 2020 в 22:10
  • Конечно извиняюсь но я Pyton не знаю так что реализовать на нем не смогу тем более с применением библиотек. 14 авг 2020 в 6:05

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.