Как в ЕГЭ · 37 из 42
№24. Не больше K нужных букв
По мотивам задания №24, второй его вид. Строка из заглавных латинских букв, до миллиона символов. Найдите самую длинную подстроку, в которой заданная буква встречается не больше K раз. Перебор всех подстрок не закончится; справляются двумя указателями — окном, у которого правый край идёт вперёд, а левый подтягивается, когда нужной буквы в окне стало слишком много.
Что сделать
Найдите длину самой длинной подстроки, где буква bukva встречается не больше k раз.
Что приходит
s— строка из заглавных латинских букв, до миллиона символовbukva— какую букву считаемk— сколько раз она может встретиться, от 0
Что вернуть
Длину самой длинной подходящей подстроки; у пустой строки — 0.
Допишите функцию dlinneyshaya_s_k в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
Строка ABXCDXEFXG, буква X, k = 1. Подстроки с одним X: ABXCD, CDXEF, EFXG — самые длинные из них по пять символов, ответ 5.
dlinneyshaya_s_k("ABXCDXEFXG", "X", 1)
5
Подстрока — символы, идущие подряд; пустая подстрока тоже годится, так что ответ не меньше 0. При k = 0 нужна самая длинная подстрока совсем без этой буквы.
Строка бывает длиной в миллион символов — решение должно справиться за один проход двумя указателями.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.