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.
According to the problem statement, each '1' can be swapped left any number of times, so each '1' can choose the largest unpicked number to its left. We can maintain these candidates with a max-heap.
Traverse the string s: for each position i, push the corresponding number nums[i] into the max-heap; if s[i] = '1', pop the maximum from the heap and add it to the answer.
After the traversal, the accumulated sum is the maximum score.
The time complexity is O(n log n) and the space complexity is O(n), where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| 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 |
Maximum Score After Binary Swaps | LeetCode 3781 | Biweekly Contest 172 • Sanyam IIT Guwahati • 542 views views
Watch 9 more video solutions →Practice Maximum Score After Binary Swaps with our built-in code editor and test cases.
Practice on FleetCode