Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии строка \(t\) состоит из «0», «1» и «?». Вы можете делать взломы только в том случае, если решили все версии этой задачи.
У Кевина есть бинарная строка \(s\) длины \(n\). Кевин может выполнять следующую операцию:
- Выбрать два соседних блока строки \(s\) и поменять их местами.
Блок — это максимальная по включению подстрока\(^{\text{∗}}\) из одинаковых символов. Формально, обозначим подстроку \(s_l s_{l+1} \ldots s_r\) как \(s[l,r]\). Тогда \(s[l,r]\) является блоком, если выполняются все условия:
- \(l=1\) или \(s_l\not=s_{l-1}\).
- \(s_l=s_{l+1} = \ldots = s_{r}\).
- \(r=n\) или \(s_r\not=s_{r+1}\).
Соседними блоками являются два блока \(s[l_1,r_1]\) и \(s[l_2,r_2]\), для которых \(r_1+1=l_2\).
Например, если \(s=\mathtt{000}\,\mathbf{11}\,\mathbf{00}\,\mathtt{111}\), Кевин может выбрать два блока \(s[4,5]\) и \(s[6,7]\) и поменять их местами, преобразовав \(s\) в \(\mathtt{000}\,\mathbf{00}\,\mathbf{11}\,\mathtt{111}\).
Дана строка \(t\) длины \(n\), состоящая из символов «0», «1» и «?». Кевин хочет определить минимальное количество операций, необходимых для получения строки, для которой выполняется следующее условие: для любого индекса \(i\) (\(1\le i\le n\)), если \(t_i\not=\) '?', то \(s_i=t_i\). Если это невозможно, выведите \(-1\).
Примечание
В первом наборе первого примера возможная последовательность операций приведена в условии.
Во втором наборе первого примера можно применить такую последовательность операций:
- Переставить блоки \([2, 2], [3, 3]\): \(s\) станет \(\mathtt{001101}\).
- Переставить блоки \([3, 4], [5, 5]\): \(s\) станет \(\mathtt{000111}\).
- Переставить блоки \([1, 3], [4, 6]\): \(s\) станет \(\mathtt{111000}\).
В первом наборе второго примера можно применить такую последовательность операций:
- Переставить блоки \([1, 1], [2, 2]\): \(s\) станет \(\mathtt{100101}\).
- Переставить блоки \([4, 4], [5, 5]\): \(s\) станет \(\mathtt{100011}\).