Taro Logo

Remove K-Balanced Substrings

Medium
Asked by:
Profile picture
3 views
Topics:
StringsStacks

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

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Does a balanced piece contain exactly k opening parentheses followed by exactly k closing parentheses?
  2. Are the pieces removed in one left-to-right pass, and is the remainder joined in its original order?
  3. If joining the leftovers creates a new balanced piece, must that new piece be removed as well?
  4. If the original text contains no removable piece, should it be returned unchanged?
  5. Is the result the remaining characters in their original relative order?

Brute Force Solution

Approach

A piece passes when every character that appears in it appears exactly k times. The search tries deleting one contiguous span, keeps the leftover when it passes, and also keeps the original text when it already passes. The shortest survivor is returned, with alphabetical order breaking ties, or an empty string when nothing survives.

Here's how the algorithm would work step-by-step:

  1. Treat a piece as acceptable when it is empty or every character that occurs in it occurs exactly k times.
  2. If the original text is acceptable, keep it as a candidate.
  3. Try deleting every contiguous span, including a span that covers the whole text.
  4. Join the part before the span with the part after it, and keep that leftover when it is acceptable.
  5. If no candidate was kept, return an empty string.
  6. Otherwise sort the candidates by length and then by text, and return the first one.

Code Implementation

from collections import Counter

def is_k_balanced(substring_to_check, balance_factor_k):
    length_of_substring = len(substring_to_check)

    # We must check every possible chunk within the given string to ensure it is k-balanced.
    for start_index in range(length_of_substring):
        for end_index in range(start_index, length_of_substring):
            chunk = substring_to_check[start_index:end_index + 1]
            digit_counts = Counter(chunk)
            for count in digit_counts.values():
                if count != balance_factor_k:
                    return False
    return True

def remove_k_balanced_substrings_brute_force(original_string, balance_factor_k):
    string_length = len(original_string)
    possible_solutions = []

    # This nested loop generates all possible substrings to remove, as described in the first step.
    for start_of_removal in range(string_length):
        for end_of_removal in range(start_of_removal, string_length):
            string_after_removal = original_string[:start_of_removal] + original_string[end_of_removal + 1:]

            # After removing a piece, we must check if the remaining string meets the k-balanced criteria.
            if is_k_balanced(string_after_removal, balance_factor_k):
                possible_solutions.append(string_after_removal)

    # If no removal results in a k-balanced string, the original string itself might be the answer.
    if is_k_balanced(original_string, balance_factor_k):
        possible_solutions.append(original_string)

    if not possible_solutions:
        return ""

    # To find the best solution, we sort by length first, then by lexicographical order for ties.
    possible_solutions.sort(key=lambda text: (len(text), text))
    
    return possible_solutions[0]

Big(O) Analysis

Time Complexity
O(n^5) – Let n be the length of the text. There are O(n^2) contiguous spans that can be deleted. Checking one leftover scans every smaller span of that leftover and counts its characters, which is O(n^3) work for a leftover of length n. Multiplying the deletions by that check gives O(n^5). Storing and sorting the survivors is smaller than those checks, so the total time is O(n^5).
Space Complexity
O(n^3) – Let n be the length of the text. In the worst case every deletion produces a distinct acceptable leftover, and the number of deletions is O(n^2). Each leftover can have length n, so storing them all takes O(n^3) memory. The character counts inside one check use a constant alphabet of parentheses. The extra space is O(n^3).

Optimal Solution

Approach

The scan starts at the right end and grows a window toward the left. A window is counted when it begins before the remembered boundary, contains exactly k distinct characters, and every one of those characters appears exactly k times. The remembered boundary then moves to that window's right end, and the returned value is the number of windows counted.

Here's how the algorithm would work step-by-step:

  1. Start the remembered boundary just past the right end, and start the count at zero.
  2. For each right end from the last character back to the first, grow the left end toward the front.
  3. Stop the window before a character that would appear more than k times.
  4. Count the window when its start is before the remembered boundary, it has exactly k distinct characters, and each of those characters appears k times.
  5. After a counted window, move the remembered boundary to that window's right end so a later window cannot overlap it.
  6. Return how many windows were counted.

Code Implementation

def count_removals(input_string, k_value):
    string_length = len(input_string)
    total_removals_count = 0

    # This marks the starting index of the longest valid k-balanced substring ending at the previous position.
    last_valid_start_index = string_length

    # Step 1: Walk along the string from right to left to align with the 'backward glance' logic.
    for current_right_boundary in range(string_length - 1, -1, -1):
        character_frequencies = {}
        unique_characters = set()

        # Step 2 & 3: Look backward from the current spot, creating a new scorecard.
        for current_left_boundary in range(current_right_boundary, -1, -1):
            current_character = input_string[current_left_boundary]
            character_frequencies[current_character] = character_frequencies.get(current_character, 0) + 1
            unique_characters.add(current_character)

            # Step 4: Stop if the balance is broken by too many occurrences of a single character.
            if character_frequencies[current_character] > k_value:
                break

            # Step 6: This optimization stops checking once we overlap with a previously found valid substring.
            if current_left_boundary < last_valid_start_index:
                number_of_unique_chars = len(unique_characters)

                if number_of_unique_chars == k_value and all(count == k_value for count in character_frequencies.values()):
                    total_removals_count += 1

                    # Step 5: Mark this spot to enable the optimization in the next main loop iteration.
                    last_valid_start_index = current_right_boundary
                    break

    return total_removals_count

Big(O) Analysis

Time Complexity
O(n^2) – Let n be the length of the text. Every character is used once as the right end of a window. From that end, the left side moves across at most n characters. Updating the counts for one added character is constant work because the alphabet is parentheses. The nested walks therefore cost O(n^2), which is the total time.
Space Complexity
O(1) – The character counts use an alphabet of parentheses, which has a fixed size of two. The remembered boundary and the window count are single numbers. No copy of the text is stored beyond the input. The extra space is O(1).

Edge Cases

The whole text is deleted
How to Handle:
The leftover is empty, the empty text passes the count test, and it wins because it is the shortest survivor.
The balance count is greater than one
How to Handle:
A nonempty piece fails whenever any character does not appear exactly that many times, so the empty leftover is the survivor.
A window contains exactly k distinct characters and each appears k times
How to Handle:
The fast scan counts that window once.
Some character inside the growing window would appear more than k times
How to Handle:
The window stops growing before that character is included.
A later window starts at or after the remembered right end
How to Handle:
That window is not counted, and the remembered end stays where the previous counted window ended.