You are given a string s containing only the characters '(' and ')', along with an integer k.

A string is called k-balanced if it consists of exactly k consecutive '(' characters immediately followed by k consecutive ')' characters — in other words, the string '(' * k + ')' * k. For example, when k = 3, the k-balanced string is "((()))".

Your task is to repeatedly remove all non-overlapping k-balanced substrings from s. After each round of removals, the remaining parts of the string are joined together, which may create new k-balanced substrings. This process continues until no k-balanced substring remains anywhere in the string.

Return the final string once no more removals can be performed.

Key points to understand:

• A substring is a contiguous sequence of characters, so the k-balanced pattern must appear as one unbroken block within s.
• Removals can cascade: deleting one k-balanced substring may bring other characters together to form a new k-balanced substring, which must then also be removed. For instance, with s = "(())" and k = 1, removing the inner "()" leaves "()", which is removed in turn, producing an empty string.
• The process only stops when the string contains no occurrence of the pattern '(' * k + ')' * k.

Examples:

• s = "(())", k = 1 → removing the inner "()" gives "()", then removing that gives "".
• s = "(()(", k = 1 → removing "()" gives "((", which contains no "()", so the answer is "((".
• s = "((()))()()()", k = 3 → removing "((()))" gives "()()()", which contains no block of three '(' followed by three ')', so the answer is "()()()".

Constraints:

• 2 <= s.length <= 10^5
• s consists only of '(' and ')'
• 1 <= k <= s.length / 2

The first thought might be to simulate the process literally: scan the string for the pattern '(' * k + ')' * k, delete every occurrence, glue the pieces back together, and repeat. The trouble is that each full pass costs O(n) time, and in the worst case we may need many passes (think of deeply nested patterns like "((((...))))" with k = 1), pushing the total cost toward O(n^2) — too slow for n up to 10^5.

The key observation is that this problem behaves exactly like classic "remove adjacent matching pairs" problems (such as removing adjacent duplicates), which are naturally solved with a stack. Why? Because a removal only ever happens at the boundary between what we've already processed and the new character we're reading. When we delete a k-balanced substring, the characters on its left and right become adjacent — and a stack handles this merging automatically: after popping, the new top of the stack is precisely the character block that just became adjacent to the incoming characters.

So instead of doing repeated passes, we process the string once, left to right, and eagerly remove a k-balanced block the moment it forms:

• A k-balanced substring is "k opens followed by k closes." This means we should detect the moment we have accumulated exactly k consecutive ')' sitting right after at least k consecutive '('.
• To check this efficiently, we don't push characters one by one. Instead, each stack entry stores a pair (character, count) — a run-length encoding. The top of the stack tells us how many identical characters are currently at the end of the processed string.
• When the top becomes (')', k) and the element below it is ('(', count >= k), we've found a k-balanced substring: pop the ')' run and subtract k from the '(' run. If that run drops to zero, pop it too.

The beautiful part is that cascading removals come for free. Suppose removing a block exposes a situation where the characters before and after it now form another k-balanced substring. Since the stack merges equal-character runs (incrementing the count rather than pushing a new entry), the very next characters we read will join the exposed run, and the same check will fire again. No second pass is ever needed.

One subtle point: why is it safe to check for exactly k closes rather than waiting to see more? Because a k-balanced substring requires the ')' run to be cut off at exactly k — and removing it as soon as the count hits k is always valid: if more ')' follow, they simply continue accumulating against the remaining '(' (whose count was at least k), allowing further removals just as the repeated-pass process would.

Each character is pushed and popped at most once (counts are only incremented or decremented), so the whole algorithm runs in O(n) time — a single linear scan replacing potentially many full-string passes.

Pattern Learn more about Stack patterns.

Data Structure: Run-Length Encoded Stack

We use a stack stk where each element is a pair [character, count], representing a run of consecutive identical characters. For example, the string "((())" would be stored as [['(', 2], [')', 2], ['(', 1)] — wait, actually as [['(', 3], [')', 2]] after merging? No — "((())" is '(', '(', '(', ')', ')' minus removals; the stack always reflects the current surviving string in compressed form.

This run-length encoding is what lets us check "are there k consecutive ')' preceded by at least k consecutive '('?" in O(1) time.

Algorithm Walkthrough

We traverse s one character c at a time and perform two phases:

Phase 1 — Push (with run merging):

• If the stack is non-empty and the top element holds the same character as c, increment its count:
  • stk[-1][1] += 1
• Otherwise, push a new run:
  • stk.append([c, 1])

This guarantees adjacent runs in the stack always alternate between '(' and ')', and crucially, when a removal exposes an older run, subsequent equal characters merge into it automatically.

Phase 2 — Check and remove a k-balanced block:

A k-balanced substring can only complete on a ')', so we check immediately after processing a closing bracket. The removal condition is:

1. c == ')' — the current character is a close,
2. len(stk) > 1 — there is a run beneath the top (which must be a '(' run, by alternation),
3. stk[-1][1] == k — the ')' run has reached exactly k,
4. stk[-2][1] >= k — the '(' run beneath has at least k opens to pair with.

When all four hold, we have found '(' * k + ')' * k at the end of the processed string, so we remove it:

• stk.pop() — discard the entire ')' run (its size is exactly k),
• stk[-1][1] -= k — consume k opens from the run below,
• if that run's count drops to 0, pop it as well, exposing whatever run lies beneath. That exposed run is now adjacent to the upcoming input characters, which is exactly how cascading removals are handled.

Final reconstruction:

After the scan, the stack holds the irreducible string in compressed form. We expand it:

• "".join(c * v for c, v in stk)

Worked Example

Take s = "(())", k = 1:

The final answer is "" — the cascading removal happened naturally within a single pass, with no need to re-scan.

Implementation

class Solution:
    def removeSubstring(self, s: str, k: int) -> str:
        stk = []
        for c in s:
            # Phase 1: push with run merging
            if stk and stk[-1][0] == c:
                stk[-1][1] += 1
            else:
                stk.append([c, 1])
            # Phase 2: remove a completed k-balanced block
            if c == ")" and len(stk) > 1 and stk[-1][1] == k and stk[-2][1] >= k:
                stk.pop()
                stk[-1][1] -= k
                if stk[-1][1] == 0:
                    stk.pop()
        return "".join(c * v for c, v in stk)

Why Checking stk[-1][1] == k (Not >= k) Is Correct

The ')' run count can never exceed k while a valid '(' run of size >= k sits below it — the moment it hits exactly k, the block is removed on that same iteration. So if a ')' run ever grows beyond k, it means the run beneath had fewer than k opens, and no k-balanced substring ending there can ever exist. Checking equality is therefore both sufficient and safe.

Complexity Analysis

• Time: O(n) — each character either increments a counter or creates a stack entry once; each removal only decrements counters or pops entries. Total stack operations are bounded by the number of characters, and the final join is linear.
• Space: O(n) — in the worst case (e.g., a string with no removable blocks), the stack stores runs covering the entire string.