Watch 10 video solutions for Maximum Score After Binary Swaps, a medium level problem involving Array, String, Greedy. This walkthrough by Sanyam IIT Guwahati has 542 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: nums = [2,1,5,2,3], s = "01010"
Output: 7
Explanation:
We can perform the following swaps:
i = 0: "01010" changes to "10010"i = 2: "10010" changes to "10100"Positions 0 and 2 contain '1', contributing nums[0] + nums[2] = 2 + 5 = 7. This is maximum score achievable.
Example 2:
Input: nums = [4,7,2,9], s = "0000"
Output: 0
Explanation:
There are no '1' characters in s, so no swaps can be performed. The score remains 0.
Constraints:
n == nums.length == s.length1 <= n <= 1051 <= nums[i] <= 109s[i] is either '0' or '1'Problem Overview: You are given a binary string and can perform swaps between characters to increase a defined score. Each swap changes the arrangement of 0s and 1s, and the goal is to choose swaps that produce the maximum possible score after all operations.
Approach 1: Brute Force Simulation (O(n2 log n) time, O(n) space)
The most direct strategy is to try all beneficial swaps between 0 and 1. For each candidate pair, simulate the swap and recompute the score impact based on how the relative ordering of bits changes. Because each swap evaluation may require scanning the string and recalculating contribution, the complexity grows quickly. This approach helps you understand how swaps affect the score but becomes impractical for large inputs.
Approach 2: Greedy with Max-Heap (Priority Queue) (O(n log n) time, O(n) space)
A better approach observes that every possible swap contributes a specific gain to the final score. Instead of recomputing the whole string repeatedly, compute the potential improvement each beneficial swap could produce. Store these gains in a max-heap so the most profitable swap is always chosen first. Each time you apply a swap, update any affected gains and push the new values back into the heap.
This greedy strategy works because the contribution of each swap can be evaluated independently and the best immediate improvement always moves the configuration closer to the optimal arrangement. Using a priority queue ensures efficient selection of the highest gain in O(log n) time. The approach processes the binary string once to compute initial gains and then repeatedly extracts the best candidate.
The implementation typically scans the string using array indexing while computing gain values derived from the relative positions of 0s and 1s. The greedy selection step is handled by a heap (priority queue). Conceptually, the method is a classic greedy optimization: always apply the swap that increases the score the most.
Recommended for interviews: Interviewers expect the greedy solution with a max-heap. Explaining the brute-force simulation first shows you understand how swaps affect the score. Transitioning to the heap-based greedy method demonstrates optimization skills and knowledge of priority queues, reducing the complexity to O(n log n) while keeping the logic clean and scalable.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Swap Simulation | O(n^2 log n) | O(n) | Useful for understanding how swaps affect score or when constraints are very small |
| Greedy with Max-Heap | O(n log n) | O(n) | General case solution; efficiently picks the highest-gain swap each step |