Codeforces Round 933 (Div. 3) |
---|
Закончено |
У Рудольфа есть строка $$$s$$$ длины $$$n$$$. Рудольф считает, что строка $$$s$$$ является некрасивой, если содержит в качестве подстроки$$$^\dagger$$$ хотя бы одну строку «pie» или хотя бы одну строку «map», в противном случае строка $$$s$$$ будет красивой.
Например, «ppiee», «mmap», «dfpiefghmap» — некрасивые строки, а «mathp», «ppiiee» — красивые строки.
Рудольф хочет сократить строку $$$s$$$, удалив некоторые символы, чтобы она стала красивой.
Главный герой не любит напрягаться, поэтому просит вас сделать строку красивой, удалив при этом минимальное количество символов. Он может удалять символы из любых позиций в строке (а не только с начала/конца строки).
$$$^\dagger$$$ Строка $$$a$$$ является подстрокой $$$b$$$, если в строке $$$b$$$ существует последовательный отрезок символов равный $$$a$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов.
Первая строка набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — длину строки $$$s$$$.
Следующая строка набора содержит строку $$$s$$$ длины $$$n$$$. Строка $$$s$$$ состоит исключительно из строчных латинских букв.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите единственное целое число — минимальное количество символов, которые нужно удалить, чтобы строка $$$s$$$ стала красивой. Если строка изначально красивая, то выведите $$$0$$$.
69mmapnapie9azabazapi8mappppie18mapmapmapmapmapmap1p11pppiepieeee
2 0 2 6 0 2
В первом наборе можно удалить, например, $$$4$$$-й и $$$9$$$-й символы, чтобы строка стала красивой.
Во втором наборе строка уже является красивой.
Название |
---|