Smallest substring with identical characters ii

String Binary Search

40.3% acceptance

Feb 24, 2026

You are given a binary string s of length n and an integer numOps. You are allowed to perform the following operation on s at most numOps times: Select any index i (where 0 <= i < n) and flip s[i]. If s[i] == '1', change s[i] to '0' and vice versa. You need to minimize the length of the longest substring of s such that all the characters in the substring are identical. Return the minimum length after the operations.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_length(s: String, num_ops: i32) -> i32 {
    // Same algorithm as version I but optimized for n up to 10^5.
    // Binary search on the answer: find minimum possible max identical-char substring length.
    // 
    // For a candidate answer mid:
    //   - If mid == 1: check if alternating pattern is achievable within numOps flips.
    //   - If mid >= 2: sum floor((L-1)/mid) over all runs of identical chars.
    
    let s: Vec<u8> = s.bytes().collect();
    let n = s.len();
    
    // Compute runs
    let mut runs: Vec<i64> = Vec::new();
    let mut i = 0;
    while i < n {
      let c = s[i];
      let mut j = i;
      while j < n && s[j] == c { j += 1; }
      runs.push((j - i) as i64);
      i = j;
    }
    
    let can_achieve = |mid: i64| -> bool {
      if mid == 1 {
        let mut ops0 = 0i64;
        let mut ops1 = 0i64;
        for (idx, &c) in s.iter().enumerate() {
          let expected0 = b'0' + (idx % 2) as u8;
          let expected1 = b'0' + (1 - idx % 2) as u8;
          if c != expected0 { ops0 += 1; }
          if c != expected1 { ops1 += 1; }
        }
        return ops0.min(ops1) <= num_ops as i64;
      }
      // mid >= 2: ops to break run of L into pieces <= mid = L / (mid+1)
      let total: i64 = runs.iter().map(|&l| l / (mid + 1)).sum();
      total <= num_ops as i64
    };
    
    let mut lo = 1i64;
    let mut hi = n as i64;
    while lo < hi {
      let mid = (lo + hi) / 2;
      if can_achieve(mid) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo as i32
  }
}