Skip to main content
Talentd

Remove K-Balanced Substrings - Solution & Explanation

MediumStringStackSimulation9 min readAsked at: Deloitte, Bloomberg
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given a string and an integer k. The task is to repeatedly remove substrings that are k-balanced until no more such substrings exist. After each removal, the remaining parts of the string join together, which may create new k-balanced segments. The goal is to simulate this process efficiently and return the final string.

Approach 1: Brute Force Simulation (O(n^2) time, O(n) space)

The most direct strategy repeatedly scans the string to detect substrings that satisfy the k-balanced condition. Once a valid segment is found, remove it and restart scanning because the merge may create new removable substrings. Implementation usually builds new strings or uses substring operations. The major cost comes from repeated rescans and string reconstruction, leading to O(n^2) time in the worst case and O(n) auxiliary space. This approach works for small inputs but quickly becomes too slow for interview constraints.

Approach 2: Stack-Based Simulation (O(n) time, O(n) space)

A more efficient strategy uses a stack to simulate the removals while scanning the string once. Push characters onto the stack and track the frequency balance of the current segment. Whenever the top portion of the stack forms a k-balanced substring, pop those characters immediately. This mirrors the effect of removing the substring and letting the remaining characters connect. Because each character is pushed and popped at most once, the total work is linear. The stack naturally models the dynamic merging behavior without repeatedly rebuilding strings.

The key insight is that substring removal problems often behave like bracket cancellation. By storing partial results in a stack, you only examine newly formed boundaries when characters are added or removed. This makes the algorithm a classic simulation problem combined with stack operations on a string.

Recommended for interviews: The stack-based solution is the expected approach. Interviewers want to see that you recognize the repeated-removal pattern and avoid rebuilding the string after every deletion. Explaining the brute force approach first shows understanding of the process, while transitioning to a stack demonstrates the optimization that reduces the complexity to linear time.

Solution

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n^2)O(n)Useful for understanding the removal process or when input size is small
Stack-Based SimulationO(n)O(n)Optimal approach for interviews and large inputs

Video Solution

Remove K-Balanced Substrings | LeetCode 3703 | Most Optimal Solution ā€¢ Sanyam IIT Guwahati ā€¢ 2,004 views views

Watch 7 more video solutions ā†’

Frequently Asked Questions

Is Remove K-Balanced Substrings easy or hard?
Remove K-Balanced Substrings is generally considered a medium-level problem. The challenge comes from recognizing that repeated substring removals should be simulated with a stack instead of repeatedly modifying the string. Once that insight is clear, the implementation becomes straightforward.
Remove K-Balanced Substrings Python/Java solution
The typical implementation uses a stack structure such as a Python list or Java Deque. Iterate through the string, push characters, maintain balance information, and pop characters when a k-balanced substring appears. The same algorithm translates directly to C++, Go, Python, or Java.
How to solve Remove K-Balanced Substrings in O(n)?
Scan the string from left to right while maintaining a stack of characters. Track the balance condition required for a substring to be k-balanced. Whenever the top portion of the stack forms such a substring, remove it immediately. This avoids repeated rescanning and keeps the overall runtime linear.
What is the best approach for Remove K-Balanced Substrings?
The most efficient approach uses a stack to simulate substring removals while scanning the string once. Characters are pushed onto the stack and removed when they form a k-balanced segment. Each character is processed at most twice (push and pop), resulting in O(n) time complexity and O(n) space.
Is Remove K-Balanced Substrings asked at Google/Amazon/Meta?
Problems involving repeated substring removal, stack simulation, and string balancing appear frequently in interviews at companies like Google, Amazon, and Meta. Variants such as removing adjacent duplicates or simplifying strings using stacks follow the same core pattern.
What data structure is used in Remove K-Balanced Substrings?
A stack is the primary data structure used to solve this problem efficiently. The stack stores characters of the partially processed string and allows quick removal when a k-balanced substring forms. Additional counters or frequency tracking help detect when the condition is satisfied.
What is the time complexity of Remove K-Balanced Substrings?
The optimal stack-based solution runs in O(n) time where n is the length of the string. Each character is pushed to the stack once and popped at most once. The space complexity is O(n) because the stack may store the remaining characters.

Ready to solve this problem?

Practice Remove K-Balanced Substrings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring