3703. Remove K-Balanced Substrings

Description

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.

 

​​​​​​​Example 1:

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

Output: ""

Explanation:

k-balanced substring is "()"

Step	Current s	k-balanced	Result s
1	(())	(())	()
2	()	()	Empty

Thus, the final string is "".

Example 2:

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

Output: "(("

Explanation:

k-balanced substring is "()"

Step	Current s	k-balanced	Result s
1	(()(	(()(	((
2	((	-	((

Thus, the final string is "((".

Example 3:

Input: s = "((()))()()()", k = 3

Output: "()()()"

Explanation:

k-balanced substring is "((()))"

Step	Current s	k-balanced	Result s
1	((()))()()()	((()))()()()	()()()
2	()()()	-	()()()

Thus, the final string is "()()()".

 

Constraints:

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

Solutions

Solution 1: Stack

We use a stack to maintain the current state of the string. Each element in the stack is a pair representing a character and its consecutive count.

Traverse each character in the string:

• If the stack is not empty and the character of the top element matches the current character, increment the count of the top element.
• Otherwise, push the current character with count 1 as a new element onto the stack.
• If the current character is ')', and there are at least two elements in the stack, and the count of the top element equals \(k\), and the count of the previous element is greater than or equal to \(k\), then pop the top element and subtract \(k\) from the count of the previous element. If the count of the previous element becomes 0, pop it as well.

After traversal, the remaining elements in the stack represent the final state of the string. We concatenate these elements in order to get the result string.

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of string \(s\).

Python3JavaC++Go

class Solution:
    def removeSubstring(self, s: str, k: int) -> str:
        stk = []
        for c in s:
            if stk and stk[-1][0] == c:
                stk[-1][1] += 1
            else:
                stk.append([c, 1])
            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)

class Solution {
    public String removeSubstring(String s, int k) {
        List<int[]> stk = new ArrayList<>();
        for (char c : s.toCharArray()) {
            if (!stk.isEmpty() && stk.get(stk.size() - 1)[0] == c) {
                stk.get(stk.size() - 1)[1] += 1;
            } else {
                stk.add(new int[] {c, 1});
            }
            if (c == ')' && stk.size() > 1) {
                int[] top = stk.get(stk.size() - 1);
                int[] prev = stk.get(stk.size() - 2);
                if (top[1] == k && prev[1] >= k) {
                    stk.remove(stk.size() - 1);
                    prev[1] -= k;
                    if (prev[1] == 0) {
                        stk.remove(stk.size() - 1);
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int[] pair : stk) {
            for (int i = 0; i < pair[1]; i++) {
                sb.append((char) pair[0]);
            }
        }
        return sb.toString();
    }
}

class Solution {
public:
    string removeSubstring(string s, int k) {
        vector<pair<char, int>> stk;
        for (char c : s) {
            if (!stk.empty() && stk.back().first == c) {
                stk.back().second += 1;
            } else {
                stk.emplace_back(c, 1);
            }
            if (c == ')' && stk.size() > 1) {
                auto& top = stk.back();
                auto& prev = stk[stk.size() - 2];
                if (top.second == k && prev.second >= k) {
                    stk.pop_back();
                    prev.second -= k;
                    if (prev.second == 0) {
                        stk.pop_back();
                    }
                }
            }
        }
        string res;
        for (auto& p : stk) {
            res.append(p.second, p.first);
        }
        return res;
    }
};

func removeSubstring(s string, k int) string {
    type pair struct {
        ch    byte
        count int
    }
    stk := make([]pair, 0)
    for i := 0; i < len(s); i++ {
        c := s[i]
        if len(stk) > 0 && stk[len(stk)-1].ch == c {
            stk[len(stk)-1].count++
        } else {
            stk = append(stk, pair{c, 1})
        }
        if c == ')' && len(stk) > 1 {
            top := &stk[len(stk)-1]
            prev := &stk[len(stk)-2]
            if top.count == k && prev.count >= k {
                stk = stk[:len(stk)-1]
                prev.count -= k
                if prev.count == 0 {
                    stk = stk[:len(stk)-1]
                }
            }
        }
    }
    res := make([]byte, 0)
    for _, p := range stk {
        for i := 0; i < p.count; i++ {
            res = append(res, p.ch)
        }
    }
    return string(res)
}

Comments