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 <= 105s consists only of '(' and ')'.1 <= k <= s.length / 2When 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:
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:
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]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:
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| Case | How to Handle |
|---|---|
| The whole text is deleted | 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 | 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 | The fast scan counts that window once. |
| Some character inside the growing window would appear more than k times | The window stops growing before that character is included. |
| A later window starts at or after the remembered right end | That window is not counted, and the remembered end stays where the previous counted window ended. |