У вас есть полоска бумаги с бинарной строкой \(s\) длины \(n\). Вы можете сложить бумагу между любой парой соседних цифр.
Последовательность складок считается допустимой, если после складок все символы, находящиеся друг над другом или под другим, совпадают. Обратите внимание, что все складки делаются одновременно, поэтому символы не обязательно должны совпадать между складками.
Например, вот допустимые складки для \(s = \mathtt{110110110011}\) и \(s = \mathtt{01110}\):
Длина сложенной полоски — это длина, видимая сверху после всех складок. Таким образом, для двух приведенных выше примеров после указанных выше складок длины будут равны \(7\) и \(3\) соответственно.
Обратите внимание, что для приведенной выше складки для \(s = \mathtt{01110}\), если бы мы сделали любую из двух складок по отдельности, это была бы недопустимая последовательность складок. Однако, поскольку мы не проверяем допустимость до тех пор, пока все складки не будут сделаны, эта последовательность складок допустима.
После выполнения последовательности допустимых складок, какова минимальная длина полоски, которую вы можете получить?
Примечание
Для первого примера одной из оптимальных последовательностей складок является складывание полоски посередине, что приводит к полоске длиной 3.
Третий и четвертый примеры соответствуют изображениям выше. Обратите внимание, что складка, показанная выше для \(s = \mathtt{110110110011}\), не является минимальной по длине.