Medium

题目描述

给你一个由 ‘(’ 和 ‘)’ 组成的字符串 s，以及一个整数 k。

如果一个字符串恰好由 k 个连续的 ‘(’ 后跟 k 个连续的 ‘)’ 组成，即 ‘(’ * k + ‘)’ * k，那么这个字符串就是 k平衡的。

例如，如果 k = 3，那么 k平衡字符串是 “((()))"。

你必须重复地从 s 中移除所有不重叠的 k平衡子串，然后将剩余部分连接起来。继续这个过程直到不存在 k平衡子串为止。

返回所有可能移除后的最终字符串。

示例 1：

输入：s = "(())", k = 1
输出：""
解释：
k平衡子串是 "()"

示例 2：

输入：s = "(()(", k = 1
输出："(("
解释：
k平衡子串是 "()"

示例 3：

输入：s = "((()))()()()", k = 3
输出："()()()"
解释：
k平衡子串是 "((()))"

约束条件：

  • 2 <= s.length <= 10^5
  • s 只包含 ‘(’ 和 ‘)’
  • 1 <= k <= s.length / 2

解题思路

这道题需要重复移除所有 k平衡子串，直到无法再移除为止。关键观察是，只有当连续的 k 个 ‘(’ 后面紧跟着连续的 k 个 ‘)’ 时，才能形成一个 k平衡子串。

核心思路：

  1. 使用栈来存储连续字符的计数
  2. 采用游程编码（run-length encoding）的思想，将连续相同字符压缩为 (字符, 计数) 的形式
  3. 当栈顶是 ‘(’ 且当前处理的是 ‘)’，且两者的计数都 >= k 时，可以进行消除操作
  4. 消除时，如果恰好等于 k，则完全移除；如果大于 k，则减去 k

算法流程：

  1. 遍历字符串，对连续相同字符进行计数
  2. 当字符发生变化时，检查是否能与栈顶进行匹配消除
  3. 如果栈顶是 ‘(’ 且当前是 ‘)’，且两者计数都 >= k，则进行消除
  4. 重复此过程直到无法再消除
  5. 最后将栈中剩余的字符还原为字符串

这个方法的优势在于避免了暴力搜索，通过栈的特性和游程编码，能够高效地处理大规模输入。

代码实现

class Solution {
public:
    string removeSubstring(string s, int k) {
        vector<pair<char, int>> stack;
        
        int i = 0;
        while (i < s.length()) {
            char ch = s[i];
            int count = 0;
            
            // Count consecutive characters
            while (i < s.length() && s[i] == ch) {
                count++;
                i++;
            }
            
            // Try to match and remove with stack top
            while (!stack.empty() && stack.back().first == '(' && ch == ')' && 
                   stack.back().second >= k && count >= k) {
                int leftCount = stack.back().second;
                stack.pop_back();
                
                leftCount -= k;
                count -= k;
                
                if (leftCount > 0) {
                    stack.push_back({'(', leftCount});
                }
            }
            
            if (count > 0) {
                stack.push_back({ch, count});
            }
        }
        
        // Build result string
        string result = "";
        for (auto& p : stack) {
            result += string(p.second, p.first);
        }
        
        return result;
    }
};

class Solution:
    def removeSubstring(self, s: str, k: int) -> str:
        stack = []
        i = 0
        
        while i < len(s):
            ch = s[i]
            count = 0
            
            # Count consecutive characters
            while i < len(s) and s[i] == ch:
                count += 1
                i += 1
            
            # Try to match and remove with stack top
            while (stack and stack[-1][0] == '(' and ch == ')' and 
                   stack[-1][1] >= k and count >= k):
                left_count = stack[-1][1]
                stack.pop()
                
                left_count -= k
                count -= k
                
                if left_count > 0:
                    stack.append(('(', left_count))
            
            if count > 0:
                stack.append((ch, count))
        
        # Build result string
        result = ""
        for ch, cnt in stack:
            result += ch * cnt
        
        return result

public class Solution {
    public string RemoveSubstring(string s, int k) {
        var stack = new List<(char ch, int count)>();
        int i = 0;
        
        while (i < s.Length) {
            char ch = s[i];
            int count = 0;
            
            // Count consecutive characters
            while (i < s.Length && s[i] == ch) {
                count++;
                i++;
            }
            
            // Try to match and remove with stack top
            while (stack.Count > 0 && stack[stack.Count - 1].ch == '(' && ch == ')' && 
                   stack[stack.Count - 1].count >= k && count >= k) {
                int leftCount = stack[stack.Count - 1].count;
                stack.RemoveAt(stack.Count - 1);
                
                leftCount -= k;
                count -= k;
                
                if (leftCount > 0) {
                    stack.Add(('(', leftCount));
                }
            }
            
            if (count > 0) {
                stack.Add((ch, count));
            }
        }
        
        // Build result string
        var result = new StringBuilder();
        foreach (var (ch, cnt) in stack) {
            result.Append(new string(ch, cnt));
        }
        
        return result.ToString();
    }
}

var removeSubstring = function(s, k) {
    const stack = [];
    let i = 0;
    
    while (i < s.length) {
        const ch = s[i];
        let count = 0;
        
        // Count consecutive characters
        while (i < s.length && s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个字符最多被处理常数次，总体为线性时间
空间复杂度O(n)栈最多存储 O(n/k) 个元素，每个元素占用常数空间