Минимизируйте стоимость переворачивания или свопов, чтобы сделать двоичную строку сбалансированной.

Для заданной двоичной строки S размера N (где N четно) задача состоит в том, чтобы найти минимальную стоимость уравновешивания данной двоичной строки путем перестановки одного из соседних разных символов за 1 единицу или замены символов по индексам i и j такие, что (i < j) ценой (j – i) единицы . Если невозможно сделать строку сбалансированной, выведите «-1» .

A binary string is balanced if it can be reduced to an empty string by deleting two consecutive alternating characters at once and then concatenating the remaining characters.

Примеры:

Input: S = “110110”
Output: 1
Explanation: Following operations are performed:
Operation 1: As the adjacent characters at indices 0 and 1 are different, flipping S[0] modifies S to “010110”. Cost = 1.

After completing the above operations, the given string becomes balanced, as it can be reduced to an empty string by deleting two consecutive alternating characters.
Therefore, the total cost is 1.

Input: S = “11100”
Output: -1

Подход: Данная проблема может быть решена на основе наблюдений, что переворачивание соседних разных символов является более оптимальным, чем использование перестановки символов, и положение 0 и 1 в строке не имеет значения. Выполните следующие шаги, чтобы решить проблему:

• Если все символы равны, то сделать строку сбалансированной невозможно. Поэтому выведите «-1» .
• Сохраните количество 1 и 0 в переменных, скажем, count1 и count0 соответственно.
• Сохраните абсолютную разницу count1 и count0 в переменной K .
• Теперь переверните символы K/2 , чтобы сделать строку сбалансированной, и выведите в результате значение K/2 .

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

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