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

Для заданной двоичной строки str задача состоит в том, чтобы найти максимально возможное значение ИЛИ любых двух подстрок двоичной строки str .

Примеры:

Input: str = “1110010”
Output: “1111110”
Explanation: On choosing the substring “1110010” and “11100” we get the OR value as “1111110” which is the maximum value.

Input: str = “11010”
Output: “11111”
Explanation: On choosing the substring “11010” and “101” we get the OR value as “11111” which is the maximum value.

Подход: Это можно решить, используя следующую идею.

We can consider the whole string as one of the substring and the other substring should be chosen in such a way that the most significant 0^th bit should be set as 1 so that the value get maximised.

Выполните шаги, указанные ниже, чтобы решить проблему:

• Удалите начальные 0 из строки str .
• Теперь пройдитесь по остальной части массива и сохраните ее в другой строке (скажем, str1 ).
• Инициализируйте другую строку (скажем, str2 ), чтобы сохранить максимально возможное побитовое ИЛИ.
• Найдите старший бит со значением '0' (скажем, k ) в строке str1.
  • Кроме того, продолжайте добавлять «1» в строку str2 , пока не будет достигнуто k .
• Если k является концом строки, верните str1 в качестве ответа [потому что в нем установлены все биты].
• В противном случае str1 будет сдвинута вправо такое количество раз, что старший бит set находится в той же позиции, что и k .
• Теперь найдите ИЛИ этих двух строк следующим образом:
  • Итерация от i = 0 до размера str1 :
    • Если установлен какой-либо бит между str1[i] и str1[k] , добавьте «1» к str2 .
    • В противном случае добавьте «0».
    • Приращение k . Если k достигает m, остановите итерацию.
• Верните str2 в качестве требуемого ответа,

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

Временная сложность: O(N), где N — длина строки.
Вспомогательное пространство: O(N)