Longest substring of one repeating character

Array String Segment Tree Ordered Set

34.2% acceptance

Feb 25, 2026

322

You are given a 0-indexed string s. You are also given a 0-indexed string queryCharacters of length k and a 0-indexed array of integer indices queryIndices of length k, both of which are used to describe k queries. The ith query updates the character in s at index queryIndices[i] to the character queryCharacters[i]. Return an array lengths of length k where lengths[i] is the length of the longest substring of s consisting of only one repeating character after the ith query is performed.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

#[derive(Clone)]
struct Node {
  len: usize,
  max_run: usize,
  lc: u8, ll: usize,
  rc: u8, rl: usize,
}

impl Node {
  fn leaf(c: u8) -> Self {
    Node { len: 1, max_run: 1, lc: c, ll: 1, rc: c, rl: 1 }
  }
  fn merge(l: &Node, r: &Node) -> Node {
    let mut max_run = l.max_run.max(r.max_run);
    if l.rc == r.lc {
      max_run = max_run.max(l.rl + r.ll);
    }
    let lc = l.lc;
    let ll = if l.ll == l.len && l.rc == r.lc { l.len + r.ll } else { l.ll };
    let rc = r.rc;
    let rl = if r.rl == r.len && r.lc == l.rc { r.len + l.rl } else { r.rl };
    Node { len: l.len + r.len, max_run, lc, ll, rc, rl }
  }
}

struct SegTree { nodes: Vec<Node> }

impl SegTree {
  fn build(s: &[u8]) -> Self {
    let n = s.len();
    let mut nodes = vec![Node::leaf(0); 4 * n];
    Self::build_rec(&mut nodes, s, 1, 0, n - 1);
    SegTree { nodes }
  }
  fn build_rec(nodes: &mut Vec<Node>, s: &[u8], v: usize, l: usize, r: usize) {
    if l == r {
      nodes[v] = Node::leaf(s[l]);
      return;
    }
    let mid = (l + r) / 2;
    Self::build_rec(nodes, s, 2*v, l, mid);
    Self::build_rec(nodes, s, 2*v+1, mid+1, r);
    let (left, right) = (nodes[2*v].clone(), nodes[2*v+1].clone());
    nodes[v] = Node::merge(&left, &right);
  }
  fn update(&mut self, v: usize, l: usize, r: usize, pos: usize, c: u8) {
    if l == r {
      self.nodes[v] = Node::leaf(c);
      return;
    }
    let mid = (l + r) / 2;
    if pos <= mid { self.update(2*v, l, mid, pos, c); }
    else { self.update(2*v+1, mid+1, r, pos, c); }
    let (left, right) = (self.nodes[2*v].clone(), self.nodes[2*v+1].clone());
    self.nodes[v] = Node::merge(&left, &right);
  }
}

impl Solution {
  pub fn longest_repeating(s: String, query_characters: String, query_indices: Vec<i32>) -> Vec<i32> {
    let bytes: Vec<u8> = s.bytes().collect();
    let n = bytes.len();
    let mut seg = SegTree::build(&bytes);
    let qc: Vec<u8> = query_characters.bytes().collect();
    let mut result = Vec::with_capacity(query_indices.len());
    for (i, &idx) in query_indices.iter().enumerate() {
      seg.update(1, 0, n - 1, idx as usize, qc[i]);
      result.push(seg.nodes[1].max_run as i32);
    }
    result
  }
}