Most bitwise OR on of any two Substrings of given Binary String

Given a binary string str, the duty is to seek out the utmost potential OR worth of any two substrings of the binary string str.

Examples:

Enter: str = “1110010”
Output: “1111110”
Rationalization: On selecting the substring “1110010” and “11100” we get the OR worth as “1111110” which is the utmost worth.

Enter: str = “11010”
Output: “11111”
Rationalization: On selecting the substring “11010” and “101” we get the OR worth as “11111” which is the utmost worth.

Strategy: This may be solved utilizing the next concept.

We will think about the entire string as one of many substring and the opposite substring needs to be chosen in such a method that essentially the most vital 0^th bit needs to be set as 1 in order that the worth get maximised.

Comply with the steps talked about under to resolve the issue:

• Take away the main 0s from the string str.
• Now traverse by way of the remainder of the array and retailer that in one other string (say str1).
• Initialize one other string (say str2) to retailer the utmost potential bitwise OR.
• Discover essentially the most vital bit with worth ‘0’ (say okay) in str1.
  • Additionally, carry on including the ‘1’s in str2 until okay is reached.
• If okay is the tip of the string, return str1 as the reply [because it has all the bits set].
• In any other case, str1 will likely be proper shifted that many occasions such that essentially the most vital setbit is on the identical place as okay.
• Now discover the OR of those two strings within the following method:
  • Iterate from i = 0 to measurement of str1:
    • If any bit between str1[i] and str1[k] is about, append ‘1’ to str2.
    • In any other case, append ‘0’.
    • Increment okay. If okay reaches m, cease the iteration.
• Return str2 because the required reply,

Under is the implementation of the above method.

Time Complexity: O(N), the place N is the size of the string.
Auxiliary House: O(N)