Longest balanced substring after one swap

13.2% acceptance

May 14, 2026

119

You are given a binary string s consisting only of characters '0' and '1'. A string is balanced if it contains an equal number of '0's and '1's. You can perform at most one swap between any two characters in s. Then, you select a balanced substring from s. Return an integer representing the maximum length of the balanced substring you can select.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_balanced(s: String) -> i32 {
    use std::collections::HashMap;
    let bytes = s.as_bytes();
    let n = bytes.len();
    let total_ones: i32 = bytes.iter().filter(|&&b| b == b'1').count() as i32;
    let total_zeros = n as i32 - total_ones;
    let mut f = vec![0i32; n + 1];
    let mut ones = 0i32;
    for i in 0..n {
      if bytes[i] == b'1' { ones += 1; }
      f[i + 1] = 2 * ones - (i as i32 + 1);
    }
    let mut by_pf: HashMap<(i32, i32), Vec<i32>> = HashMap::new();
    for i in 0..=n {
      let parity = (i & 1) as i32;
      by_pf.entry((parity, f[i])).or_insert_with(Vec::new).push(i as i32);
    }
    let mut best = 0i32;
    for indices in by_pf.values() {
      if indices.len() >= 2 {
        let diff = indices[indices.len() - 1] - indices[0];
        if diff > best { best = diff; }
      }
    }
    let limit_b = 2 * total_zeros;
    let limit_c = 2 * total_ones;
    for ((parity, fl), l_indices) in by_pf.iter() {
      if let Some(r_indices) = by_pf.get(&(*parity, fl + 2)) {
        for &l in l_indices {
          let upper = l + limit_b;
          let pos = r_indices.partition_point(|&r| r <= upper);
          if pos > 0 {
            let r = r_indices[pos - 1];
            if r > l && r - l > best {
              best = r - l;
            }
          }
        }
      }
      if let Some(r_indices) = by_pf.get(&(*parity, fl - 2)) {
        for &l in l_indices {
          let upper = l + limit_c;
          let pos = r_indices.partition_point(|&r| r <= upper);
          if pos > 0 {
            let r = r_indices[pos - 1];
            if r > l && r - l > best {
              best = r - l;
            }
          }
        }
      }
    }
    best
  }
}