Вам дана бинарная строка\(^{\dagger}\). Пожалуйста, найдите минимальное количество частей, которые вам нужно отрезать, чтобы полученные части можно было переставить в отсортированную бинарную строку.
Обратите внимание, что:
- каждый символ должен принадлежать ровно одной из частей;
- части должны быть непрерывными подстроками исходной строки;
- вам нужно использовать все части при перестановке.
\(^{\dagger}\) Бинарная строка — это строка, состоящая из символов \(\texttt{0}\) и \(\texttt{1}\). Отсортированная бинарная строка — это бинарная строка, в которой все символы \(\texttt{0}\) идут перед всеми символами \(\texttt{1}\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество частей, необходимое для того, чтобы можно было переставить строку в отсортированную бинарную строку.
Примечание
Первый пример изображен в условии. Можно доказать, что вам понадобится не менее \(3\) частей.
Во втором и третьем примерах случаях бинарная строка уже отсортирована, поэтому нужна только \(1\) часть.
В четвертом примере вам нужно сделать один разрез между двумя символами и переставить их, чтобы получить строку \(\texttt{01}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
11010
00000000
1
10
0001111
0110
|
3
1
1
2
1
2
|