Maximum bitwise OR on of any two Substrings of given Binary String – GeeksforGeeks

Given a binary string str, the task is to find the maximum possible OR value of any two substrings of the binary string str.

Examples:

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.

Approach: This can be solved using the following idea.

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.

Follow the steps mentioned below to solve the problem:

• Remove the leading 0s from the string str.
• Now traverse through the rest of the array and store that in another string (say str1).
• Initialize another string (say str2) to store the maximum possible bitwise OR.
• Find the most significant bit with value ‘0’ (say k) in str1.
  • Also, keep on adding the ‘1’s in str2 till k is reached.
• If k is the end of the string, return str1 as the answer [because it has all the bits set].
• Otherwise, str1 will be right shifted that many times such that the most significant setbit is at the same position as k.
• Now find the OR of these two strings in the following way:
  • Iterate from i = 0 to size of str1:
    • If any bit between str1[i] and str1[k] is set, append ‘1’ to str2.
    • Otherwise, append ‘0’.
    • Increment k. If k reaches m, stop the iteration.
• Return str2 as the required answer,

Below is the implementation of the above approach.

Time Complexity: O(N), where N is the length of the string.
Auxiliary Space: O(N)