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

Опубликовано: 27 Февраля, 2023

Для заданной двоичной строки S четного размера, содержащей только 0 и 1, задача состоит в том, чтобы найти минимальные перестановки (то есть 0 в 1 или 1 в 0 ), чтобы каждый непрерывный подсегмент, содержащий один и тот же бит, был четного размера.

Примеры:

Input: S = “1110011000 “
Output: 3
Explanation: Change S[2], S[5] and S[6] to ‘0’. 
After that S becomes “1100000000”, it can be divided into 
“11” and “00000000”, which have lengths 2 and 8 respectively. 
There are other ways to operate 3 times such as 
“1111110000”, “1100001100”, “1111001100”. 

Input: 100110 
Output: 3
Explanation: The given string can be converted into 000000 
with 3 operations or 111111.

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

It can be said that we have to divide the string into many adjacent binaries with the length of 2 where the strings will be either 00 or 11. So, we have to only take care of sequence where s[i] != s[i+1] 

  • Now in order to find a minimum operation sequence like  “1011”  should be converted to “1111”  and  “0100” should be converted to “0000”. 
  • So, the minimum number of operations is 1. Hence once we make s[i] = s[i + 1] we will move i to i+2  to check whether they are equal or not.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Итерация от i = 0 до N-1 :
    • Проверьте, совпадает ли S[i] с S[i+1] .
    • Если они одинаковы, то переворот битов не требуется.
    • В противном случае увеличьте количество переворотов на 1.
    • После каждой проверки двигайтесь от i к i+2 .
  • Подсчитанное общее количество бросков является требуемым минимальным ответом.

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

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

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