Maximize active section with trade ii

Array String Binary Search Segment Tree

20.4% acceptance

Feb 25, 2026

You are given a binary string s of length n, where: '1' represents an active section. '0' represents an inactive section. You can perform at most one trade to maximize the number of active sections in s. In a trade, you: Convert a contiguous block of '1's that is surrounded by '0's to all '0's. Afterward, convert a contiguous block of '0's that is surrounded by '1's to all '1's. Additionally, you are given a 2D array queries, where queries[i] = [li, ri] represents a substring s[li...ri]. For each query, determine the maximum possible number of active sections in s after making the optimal trade on the substring s[li...ri]. Return an array answer, where answer[i] is the result for queries[i]. Note For each query, treat s[li...ri] as if it is augmented with a '1' at both ends, forming t = '1' + s[li...ri] + '1'. The augmented '1's do not contribute to the final count. The queries are independent of each other.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_active_sections_after_trade(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = s.len();
    let sb: Vec<u8> = s.bytes().map(|b| b - b'0').collect();

    // prefix sum of 1s
    let mut pre = vec![0i32; n + 1];
    for i in 0..n {
      pre[i + 1] = pre[i] + sb[i] as i32;
    }

    // collect zero-groups (start, end) inclusive
    let mut zg: Vec<(usize, usize)> = Vec::new();
    let mut i = 0;
    while i < n {
      if sb[i] == 0 {
        let st = i;
        while i < n && sb[i] == 0 { i += 1; }
        zg.push((st, i - 1));
      } else {
        i += 1;
      }
    }
    let m = zg.len();

    // pair_val[i] = len(zg[i]) + len(zg[i+1])
    let mut pv: Vec<i32> = Vec::new();
    for i in 0..m.saturating_sub(1) {
      pv.push((zg[i].1 - zg[i].0 + 1) as i32 + (zg[i + 1].1 - zg[i + 1].0 + 1) as i32);
    }

    // sparse table for range max over pv
    let p = pv.len();
    let levels = if p == 0 { 1 } else { (usize::BITS - p.leading_zeros()) as usize + 1 };
    let mut sp = vec![vec![0i32; p.max(1)]; levels];
    for i in 0..p { sp[0][i] = pv[i]; }
    for j in 1..levels {
      for i in 0..p {
        let half = 1usize << (j - 1);
        sp[j][i] = sp[j-1][i];
        if i + half < p {
          sp[j][i] = sp[j][i].max(sp[j-1][i + half]);
        }
      }
    }
    let rmq = |l: usize, r: usize| -> i32 {
      if l > r || p == 0 { return 0; }
      let k = (usize::BITS - (r - l + 1).leading_zeros()) as usize - 1;
      let right_start = r + 1 - (1 << k);
      sp[k][l].max(sp[k][right_start])
    };

    let total_ones = pre[n]; // total 1s in all of s (outside [l,r] are unchanged)

    let mut ans = Vec::new();
    for q in &queries {
      let (l, r) = (q[0] as usize, q[1] as usize);

      // find zero groups overlapping [l, r]
      // first group: zg[a].end >= l => partition_point where zg.end < l
      let a = zg.partition_point(|&(_, e)| e < l);
      // last group: zg[b].start <= r => last i where zg[i].start <= r
      let b_e = zg.partition_point(|&(s, _)| s <= r);
      if b_e == 0 || a >= b_e {
        ans.push(total_ones);
        continue;
      }
      let b = b_e - 1;
      if a >= b {
        ans.push(total_ones);
        continue;
      }

      let clip = |zi: usize| -> i32 {
        (zg[zi].1.min(r) as i32 - zg[zi].0.max(l) as i32 + 1).max(0)
      };

      let mut max_gain = 0i32;

      // boundary pairs
      max_gain = max_gain.max(clip(a) + clip(a + 1));
      max_gain = max_gain.max(clip(b - 1) + clip(b));

      // interior pairs: both groups fully within [l,r]
      // first fully interior: zg[i].start >= l => partition_point
      let a2 = zg.partition_point(|&(s, _)| s < l);
      // last fully interior: zg[i].end <= r => last i where zg[i].end <= r
      let b2_e = zg.partition_point(|&(_, e)| e <= r);
      if b2_e > 0 {
        let b2 = b2_e - 1;
        if a2 < b2 {
          // pair indices in pv: a2 to b2-1
          max_gain = max_gain.max(rmq(a2, b2 - 1));
        }
      }

      ans.push(total_ones + max_gain);
    }
    ans
  }
}