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

Опубликовано: 22 Сентября, 2022

Даны две двоичные строки A и B длины N , задача состоит в том, чтобы преобразовать строку A в B , либо перевернув любой символ A , либо переставив соседние символы A минимальное количество раз. Если невозможно сделать обе строки равными, выведите -1 .

Примеры:

Input: A = “10010010”, B = “00001000”  
Output: 3
Explanation:
Operation 1: Flipping A[0] modifies A to “00010010”.
Operation 2: Flipping A[6] modifies A to “00010000”.
Operation 3: Swapping A[3] and A[4] modifies A to “00001000” 
Therefore, the total number of operations is 3.

Input: A = “11”, B = “00”  
Output: 3

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

  • Инициализируйте переменную, скажем, ans, для сохранения требуемого результата.
  • Пройдите строку A , используя переменную, скажем i , и выполните следующие операции:
    • Если A[i] равно B[i], то переходим к следующей итерации цикла.
    • В противном случае, если A[i] равно B[i + 1] и A[i + 1] равно B[i] , то поменяйте местами символы и увеличьте i и ans на 1 .
    • В противном случае, если A[i] не равно B[i] , то инвертировать текущий бит и увеличить an на 1 .
  • Выведите значение ans в качестве результата.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ