Как в ЕГЭ · 15 из 20
№24. Самая длинная цепочка
По мотивам задания №24. В файле экзамена — строка из миллиона символов, и нужна самая длинная цепочка подряд идущих символов, в которой одна буква встречается не больше k раз. Решение «перебрать все начала и концы» верное, но на миллионе символов оно считало бы до конца экзамена. Здесь строка приходит в функцию, и проверка меряет не только ответ, но и время.
Что сделать
Найдите длину самой длинной цепочки подряд идущих символов, где bukva встречается не больше k раз.
Что приходит
stroka— строка, длиной до миллиона символовbukva— символ, который считаемk— сколько раз он может встретиться в цепочке, от 0
Что вернуть
Длину самой длинной такой цепочки — целое число; у пустой строки — 0.
Допишите функцию dlinneyshaya в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
с графикой когда тесты пройдут, ответ вашей функции нарисуется · все задачи с графикой
В "XAXBBX" при k = 1 цепочки с одной X: "XA", "AXBB", "BBX"… Самая длинная — "AXBB", четыре символа. Ответ — 4.
dlinneyshaya("XAXBBX", "X", 1)
4
Цепочка — подряд идущие символы строки, от одного до всех. В ней bukva встречается не больше k раз. Нужна наибольшая длина. Строка до миллиона символов, время — как у всех задач: решение, которое для каждого начала перебирает концы, на длинной строке не успевает, и это часть задачи.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.