Минимум смежных свопов, необходимых для чередования двоичной строки

Для заданной двоичной строки S размера N задача состоит в том, чтобы найти минимальное количество перестановок соседних строк, необходимое для того, чтобы строка стала альтернативной. Если это невозможно сделать, то выведите -1 .

Примеры:

Input: S = “10011”
Output: 1
Explanation:
Swap index 2 and index 3 and the string becomes 10101 .

Input: S = “110100”
Output: 2
Explanation: 
First, swap index 1 and index 2 and the string becomes 101100 . 
Second, swap index 3 and index 4 and the string becomes 101010 .

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

• Инициализируйте переменные единицами и нулями как 0 , чтобы подсчитать количество нулей и единиц в строке.
• Перебрать диапазон [0, N), используя переменную i , и подсчитать количество 0 и 1 в двоичной строке.
• Проверьте базовые случаи, т. е. если N четно, то равны ли нули единицам или нет. И если N нечетно, то разница между ними должна быть 1. Если базовые случаи не удовлетворяют, то вернуть -1 .
• Инициализируйте переменную ans_1 как 0 , чтобы сохранить ответ, когда строка начинается с 1 и j как 0.
• Переберите диапазон [0, N), используя переменную i , и если s[i] равно 1 , добавьте значение abs(ji) к переменной ans_1 и увеличьте значение j на 2 .
• Точно так же инициализируйте переменную ans_0 как 0 , чтобы сохранить ответ, когда строка начинается с 1 и k как 0 .
• Переберите диапазон [0, N), используя переменную i , и если s[i] равно 0 , добавьте значение abs(k – i) к переменной ans_0 и увеличьте значение k на 2 .
• Если N четно, то в качестве результата выведите минимум ans_1 или ans_0 . В противном случае, если нулей больше, чем единиц , выведите ans_0 . В противном случае выведите ans_1 .

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

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