Maximize sum by selecting Array aspect to left of every ‘1’ of a Binary String

Given a binary string S and an array arr[] every of measurement N, we are able to choose any aspect from the Array which is to the left of (or on the identical place) the indices of ‘1’s within the given binary string. The duty is to search out the utmost attainable sum.

Examples:

Enter: arr[] = {20, 10, 30, 9, 20, 9}, string S = “011011”, N = 6
Output: 80
Rationalization: Choose 20, 10, 30 and 20 in Sum, so, Sum = 80.

Enter:  arr[] = {30, 20, 10}, string S = “000”, N = 3.
Output: 0

Method: The given drawback might be solved through the use of a precedence queue primarily based on the next thought:

Say there are Okay occurrences of ‘1’ in string S. It may be seen that we are able to prepare the characters in a means such that we are able to choose the Okay most components from the array that are to the left of the final incidence of ‘1’ in S. So we are able to use a precedence queue to get these Okay most components.

Comply with the steps to resolve this drawback:

• Initialize variable Sum = 0, Cnt = 0.
• Create a precedence queue (max heap) and traverse from i = 0 to N-1:
  • If S[i] is ‘1’, increment Cnt by 1.
  • Else, whereas Cnt > 0, add the topmost aspect of the precedence queue and decrement Cnt by 1.
  • Push the i^th aspect of the array into the precedence queue.
• After executing the loop, whereas Cnt > 0, add the topmost aspect of the precedence queue and decrement Cnt by 1.
• Eventually, return the Sum because the required reply.

Beneath is the implementation of the above method.

Time Complexity: O(N * log N)
Auxiliary Area: O(N)