Smallest substring with identical characters i

Array Binary Search Enumeration

20.4% 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 {
    // Binary search on the answer: find minimum possible max identical-char substring length.
    // 
    // For a candidate answer mid:
    //   - If mid == 1: the only way to achieve max run = 1 is alternating "0101..." or "1010...".
    //     ops needed = min(# positions matching pattern 0, # matching pattern 1) where
    //     "matching" means: the current char matches the alternating pattern (no flip needed).
    //     So ops = min(# chars != p0[i], # chars != p1[i]) where p0[i] = i%2, p1[i] = 1-i%2.
    //   - If mid >= 2: process runs of identical chars. For a run of length L,
    //     ops needed to break into pieces ≤ mid: floor((L - 1) / mid) flips.
    //     (Place one flip every 'mid' positions within the run.)
    //     Total ops = sum over all runs of floor((L-1)/mid).
    //     Achievable iff total ops <= numOps.
    
    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 {
        // For max run = 1, need alternating pattern. Two options: "0101..." or "1010...".
        // Use formula per-run: ops = L/(mid+1) = L/2, but this counts within runs only.
        // The alternating pattern check is globally correct:
        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
  }
}