Сделать двоичную строку палиндрома ровно с 0 и b 1, заменив подстановочный знак?

Дана строка S из N символов, состоящая из '?' , ' 0 ' и ' 1 ' и два целых числа a и b , задача состоит в том, чтобы найти палиндромную двоичную строку, содержащую ровно 0 и b 1 , заменив ' ? ' с ' 0 ' или ' 1 '.

Примеры:

Input: S = “10?????1”, a = 4, b = 4
Output: 10100101
Explanation: The output string is a palindromic binary string with exactly 4 0’s and 4 1’s.

Input: S = “??????”, a = 5, b = 1
Output: -1
Explanation: There does not exist any palindromic string with exactly a 0’s and b 1’s.

Подход: Данная проблема может быть решена с использованием следующих наблюдений:

• Чтобы строка S из N символов была палиндромом, S[i] = S[Ni-1] должно выполняться для всех значений i в диапазоне [0, N) .
• Если только один из S[i] и S[Ni-1] равен ' ? ', то его необходимо заменить соответствующим символом другого индекса.
• Если значение как S[i] , так и S[Ni-1] равно ' ? ', наиболее оптимальным выбором будет заменить их обоих на символ, чей требуемый счет больше.

Используя приведенные выше наблюдения, выполните следующие шаги, чтобы решить проблему:

• Пройтись по строке в диапазоне [0, N/2) и для случаев, когда только один из S[i] и S[N – i – 1] равен ' ? ', замените его соответствующим символом.
• Обновите значения a и b , вычитая количество « 0 » и « 1 » после вышеуказанной операции. Количество можно легко вычислить с помощью функции std::count.
• Теперь пройдите по заданной строке в диапазоне [0, N/2) , и если оба S[i] = ' ? ' и S[Ni-1] = ' ? ', обновите их значение символом, требуемое количество которого больше (т. е. ' 0 ', если a>b , иначе ' 1 ').
• В случае нечетной длины строки со средним символом в виде ' ? ', обновите его символом с оставшимся счетчиком.
• Если значение a = 0 и b = 0 , строка, хранящаяся в S , является необходимой строкой. В противном случае требуемая строка не существует, поэтому верните -1 .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)