Maximum score after binary swaps

Array String Greedy Heap (Priority Queue)

35.0% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_score(nums: Vec<i32>, s: String) -> i64 {
    use std::collections::BinaryHeap;
    let sb: Vec<u8> = s.bytes().collect();
    let n = nums.len();
    // Collect positions of '1's (sorted, left to right)
    let positions: Vec<usize> = (0..n).filter(|&i| sb[i] == b'1').collect();
    if positions.is_empty() { return 0; }
    // Greedy: for the i-th '1' (left to right), release all positions
    // [prev_pos+1 .. pos[i]] into a max-heap, then pick the largest.
    // This works because the i-th '1' can only move left (not past earlier '1's),
    // so the i-th chosen position must be <= pos[i].
    let mut heap: BinaryHeap<i32> = BinaryHeap::new();
    let mut sum: i64 = 0;
    let mut prev_pos = 0usize;
    for (idx, &pos) in positions.iter().enumerate() {
      let start = if idx == 0 { 0 } else { prev_pos + 1 };
      for j in start..=pos {
        heap.push(nums[j]);
      }
      prev_pos = pos;
      sum += heap.pop().unwrap() as i64;
    }
    sum
  }
}