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

Даны две двоичные строки s1[] и s2[] одинаковой длины N. Задача состоит в том, чтобы найти минимальное количество операций, чтобы сделать их равными. Выведите -1 , если это невозможно. Одна операция определяется как выбор двух соседних индексов одной двоичной строки и инвертирование символов в этих позициях, т. е. с 1 на 0 и наоборот.

Примеры:

Input: s1[] = “0101”, s2[] = “1111”
Output: 2
Explanation: Invert the characters at 1 and 2 indices in the first string and at 0 and 1 indices in the second string to make them equal as 0011. There are other ways to do also like converting to 1111, etc.

Input: s1[] = “011”, s2[] = “111”
Output: -1 

Подход: Идея состоит в том, чтобы линейно пройти обе строки и, если в каком-либо индексе символы отличаются, инвертировать i ^-й и (i+1) ^-й символы в строке s1[]. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную count как 0 , чтобы сохранить ответ.
• Переберите диапазон [0, N], используя переменную i , и выполните следующие шаги:
  • Если s1[i] не равно s2[i] , выполните следующие задачи:
    • Если s1[i] равно 1, то измените его на 0 , иначе измените на 1.
    • Точно так же, если s1[i+1] равно 1, измените его на 0 , иначе измените на 1.
    • Наконец, увеличьте значение count на 1.
• Если s1[] равно s2[], то верните значение count в качестве ответа, иначе верните -1.

Ниже приведена реализация описанного выше подхода.

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