Minimum deletions to make alternating substring

String Segment Tree

44.9% acceptance

Feb 25, 2026

You are given a string s of length n consisting only of the characters 'A' and 'B'. You are also given a 2D integer array queries of length q, where each queries[i] is one of the following: [1, j]: Flip the character at index j of s i.e. 'A' changes to 'B' (and vice versa). This operation mutates s and affects subsequent queries. [2, l, r]: Compute the minimum number of character deletions required to make the substring s[l..r] alternating. This operation does not modify s; the length of s remains n. A substring is alternating if no two adjacent characters are equal. A substring of length 1 is always alternating. Return an integer array answer, where answer[i] is the result of the ith query of type [2, l, r].

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

fn bit_update(bit: &mut Vec<i32>, mut i: usize, delta: i32, n: usize) {
  while i <= n {
    bit[i] += delta;
    i += i & i.wrapping_neg();
  }
}

fn bit_query(bit: &[i32], mut i: usize) -> i32 {
  let mut sum = 0;
  while i > 0 {
    sum += bit[i];
    i -= i & i.wrapping_neg();
  }
  sum
}

impl Solution {
  pub fn min_deletions(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = s.len();
    let mut chars: Vec<u8> = s.bytes().collect();
    let mut result = Vec::new();

    if n == 0 {
      return result;
    }

    // bad[i] = 1 if chars[i] == chars[i+1], for i in 0..n-1
    // Use a Fenwick tree (BIT) over bad[] for O(log n) range-sum queries and point updates.
    // BIT is 1-indexed; BIT position (i+1) stores bad[i].
    let m = n - 1; // number of adjacent pairs
    let mut bad: Vec<i32> = (0..m)
      .map(|i| if chars[i] == chars[i + 1] { 1 } else { 0 })
      .collect();
    let mut bit = vec![0i32; m + 2];
    for i in 0..m {
      bit_update(&mut bit, i + 1, bad[i], m);
    }

    for q in &queries {
      if q[0] == 1 {
        let j = q[1] as usize;
        chars[j] ^= b'A' ^ b'B'; // flip 'A' <-> 'B'
        // Update pairs (j-1, j) and (j, j+1) if they exist
        for &p in &[j.wrapping_sub(1), j] {
          if p < m {
            let new_bad = if chars[p] == chars[p + 1] { 1 } else { 0 };
            if new_bad != bad[p] {
              bit_update(&mut bit, p + 1, new_bad - bad[p], m);
              bad[p] = new_bad;
            }
          }
        }
      } else {
        let l = q[1] as usize;
        let r = q[2] as usize;
        if l == r {
          result.push(0);
        } else {
          // Sum of bad[l..=r-1] = BIT.query(r) - BIT.query(l)
          let ans = bit_query(&bit, r) - bit_query(&bit, l);
          result.push(ans);
        }
      }
    }
    result
  }
}