LeetCode in Kotlin

3703. Remove K-Balanced Substrings

Medium

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 **substring** 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	(() )	(<s>**()**</s>)	()
2	()	<s>**()**</s>`	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

Solution

class Solution {
    fun removeSubstring(s: String, k: Int): String {
        val sb = StringBuilder()
        var count = 0
        for (ch in s.toCharArray()) {
            sb.append(ch)
            if (ch == '(') {
                count++
            } else {
                if (count >= k && sb.length >= 2 * k) {
                    val len = sb.length
                    var b = true
                    for (i in len - 2 * k..<len - k) {
                        if (sb[i] != '(') {
                            b = false
                            break
                        }
                    }
                    for (i in len - k..<len) {
                        if (sb[i] != ')') {
                            b = false
                            break
                        }
                    }
                    if (b) {
                        sb.delete(sb.length - 2 * k, sb.length)
                        count -= k
                    }
                }
            }
        }
        return sb.toString()
    }
}

This site is open source. Improve this page.