DSA括号问题：重复移除n-平衡子串后求剩余字符串

问题定义 #

我们称一个括号序列为平衡序列，当且仅当满足以下全部条件：

• 以左括号(开头
• 以右括号)结尾
• 任意位置的右括号数量不超过左括号数量
• 左括号总数等于右括号总数

我们称一个平衡括号序列为n-平衡序列，当且仅当它由连续n个左括号(后跟连续n个右括号)组成。

操作规则：反复执行以下步骤，直到字符串中不存在n-平衡子串：

1. 从当前字符串中移除所有n-平衡子串
2. 将删除部分左右的子串拼接成新的字符串

输入输出格式 #

输入 #

• 第一行输入测试用例总数t
• 后续2*t行，每个测试用例对应两行内容：
  • 第一行：括号字符串s
  • 第二行：整数n

约束条件 #

• 1 ≤ t ≤ 10³
• 1 ≤ |s| ≤ 10⁴
• 1 ≤ n ≤ 10²

输出 #

对每个测试用例，输出执行完所有移除操作后的剩余字符串；若剩余字符串为空，则输出-1

样例 #

输入 #

3
((())())()
2
((()))
3
))((
2

输出 #

()
-1
))((

解决方案 #

思路 #

使用栈模拟移除过程，核心是跟踪连续的左/右括号数量，当检测到连续n个左括号+连续n个右括号的组合时，直接移除该段：

1. 用栈存储整数，正数表示连续左括号的数量，负数表示连续右括号的数量
2. 遍历字符串每个字符，更新栈中对应的连续计数
3. 每次更新右括号计数后，检查栈顶是否存在n个连续左括号和n个连续右括号的组合，若是则弹出这两个计数（即移除该n-平衡子串）
4. 最后将栈中剩余的计数转换为对应的括号字符串，得到最终结果

代码实现（Python） #

def remove_n_balanced(s, n):
    stack = []
    for c in s:
        if c == '(':
            if stack and isinstance(stack[-1], int) and stack[-1] > 0:
                stack[-1] += 1
            else:
                stack.append(1)
        else:
            if stack and isinstance(stack[-1], int) and stack[-1] < 0:
                stack[-1] -= 1
            else:
                stack.append(-1)
            
            # 检查是否形成n-平衡序列，循环处理可能的连锁移除
            while len(stack) >= 2:
                right_cnt = stack[-1]
                left_cnt = stack[-2]
                if right_cnt == -n and left_cnt == n:
                    stack.pop()
                    stack.pop()
                else:
                    break
    # 重构结果字符串
    res = []
    for cnt in stack:
        if cnt > 0:
            res.append('(' * cnt)
        elif cnt < 0:
            res.append(')' * (-cnt))
    result = ''.join(res)
    return result if result else '-1'

t = int(input())
for _ in range(t):
    s = input().strip()
    n = int(input())
    print(remove_n_balanced(s, n))

代码说明 #

• 栈存储的整数简化了连续括号的计数，避免逐个存储字符，提升效率
• 循环检查连锁移除：移除某个n-平衡子串后，左右拼接的部分可能形成新的n-平衡子串，需要再次检查
• 最终将栈中剩余的计数转换为对应括号，若结果为空则返回-1

内容的提问来源于stack exchange，提问作者Prateekoctane