Remove K-Balanced Substrings - Solution & Explanation

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.