You are given an integer array nums of length n and a binary string s of the same length.

Initially, your score is 0. Each index i where s[i] = '1' contributes nums[i] to the score.

You may perform any number of operations (including zero). In one operation, you may choose an index i such that 0 <= i < n - 1, where s[i] = '0' and s[i + 1] = '1', and swap these two characters.

Return an integer denoting the maximum possible score you can achieve.

In other words, each '1' in the string can be moved to the left through any number of swaps (each swap moves a '1' one position left, past a '0'). After rearranging the '1's by moving them leftward, the score is the sum of nums[i] over all positions i where s[i] = '1'. The goal is to choose how to perform the swaps so that this total sum is as large as possible.

The key observation is that because a '1' can only move left and cannot move right, each '1' ends up occupying some position at or before its original location. Since '1's can be relocated to any earlier available spots, each '1' effectively gets to select one of the numbers at indices to its left (including its own index), without two '1's sharing the same index. To maximize the score, every '1' should claim the largest still-unclaimed value among the indices available to it.

Let's think about what the swap operation really lets us do. The only allowed swap moves a '1' one step to the left (past a '0'). A '1' can never move to the right. This means every '1' can end up at its original position or at any position before it, as long as no two '1's land on the same spot.

So the real question becomes: for each '1' in the string, which index's value should it collect? Since a '1' at position i can slide left to any earlier empty slot, it is free to "pick up" the value nums[j] for any index j <= i that isn't already taken by another '1'.

If we process the array from left to right, then by the time we reach the k-th '1', all indices up to its current position have already been seen. Together with the values from earlier '1's positions, this forms a pool of candidate numbers. Each '1' wants the biggest value it can grab, and earlier choices should never block later ones from doing better.

This naturally leads to a greedy idea: keep a running collection of all values seen so far, and whenever we hit a '1', take the largest value currently available. Because every value added stays a valid candidate for all '1's that come afterward, always grabbing the current maximum for each '1' guarantees the overall sum is maximized.

To efficiently fetch and remove the largest available value at each '1', a max-heap is the perfect tool. We push each nums[i] into the heap as we scan, and for every '1' we pop the heap's maximum and add it to the answer. Since Python's heapq is a min-heap, we push negated values -x so that popping gives us the largest original number.

Pattern Learn more about Greedy and Heap (Priority Queue) patterns.

Solution 1: Max-Heap

According to the problem statement, each '1' can be swapped left any number of times, so each '1' can choose the largest unpicked number among the indices to its left (including its own). We maintain these candidate numbers with a max-heap.

We traverse the string s together with the array nums from left to right. For each position i:

1. Push the current value nums[i] into the max-heap. This makes it a candidate that can be picked by the current '1' or any later '1'.
2. If s[i] = '1', pop the maximum value from the heap and add it to the answer. This represents the current '1' grabbing the best still-available value.

After the traversal finishes, the accumulated sum is the maximum score.

Since Python's heapq only provides a min-heap, we store the negated values -x. Pushing -x and popping the smallest element gives us the largest original number, so we subtract the popped value (ans -= heappop(pq)) to add its true positive amount.

Walking through the code:

• pq = [] initializes an empty heap, and ans = 0 initializes the score.
• heappush(pq, -x) adds every number as a candidate as we scan.
• When c == "1", ans -= heappop(pq) removes the current maximum and adds it to the answer.
• Finally, return ans gives the maximum achievable score.

The time complexity is O(n × log n), where n is the length of nums, because each element is pushed and possibly popped from the heap once, and each heap operation costs O(log n). The space complexity is O(n) for the heap.