Remove k balanced substrings

String Stack Simulation

32.4% acceptance

Feb 24, 2026

128

You are given a string s consisting of '(' and ')', and an integer k. A string is k-balanced if it is exactly k consecutive '(' followed by k consecutive ')', i.e., '(' * k + ')' * k. For example, if k = 3, k-balanced is "((()))". You must repeatedly remove all non-overlapping k-balanced substrings from s, and then join the remaining parts. Continue this process until no k-balanced substring exists. Return the final string after all possible removals.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn remove_substring(s: String, k: i32) -> String {
    let k = k as usize;
    // Stack stores run-length encoded (char, count) pairs.
    // After pushing each ')', check if the top two runs form k '(' + k ')'
    // and collapse them; repeat until no more collapses are possible.
    let mut stack: Vec<(u8, usize)> = Vec::new();

    for c in s.bytes() {
      match stack.last_mut() {
        Some(top) if top.0 == c => top.1 += 1,
        _ => stack.push((c, 1)),
      }

      if c == b')' {
        loop {
          let n = stack.len();
          if n >= 2
            && stack[n - 1].0 == b')' && stack[n - 1].1 >= k
            && stack[n - 2].0 == b'(' && stack[n - 2].1 >= k
          {
            stack[n - 1].1 -= k;
            stack[n - 2].1 -= k;
            // Remove zero-count entries (check in reverse order)
            if stack.last().map_or(false, |t| t.1 == 0) {
              stack.pop();
            }
            if stack.last().map_or(false, |t| t.1 == 0) {
              stack.pop();
            }
          } else {
            break;
          }
        }
      }
    }

    stack
      .iter()
      .flat_map(|(c, count)| std::iter::repeat(*c as char).take(*count))
      .collect()
  }
}