Approaches
💡
Intuition
Time UnknownSpace Unknown
The brute force approach checks every possible way to balance the parentheses string by inserting characters. This is straightforward but inefficient, as it involves generating all combinations and checking their validity.
⚙️
Algorithm
3 steps- 1Step 1: Generate all possible strings by inserting '(' and ')' at every possible position.
- 2Step 2: For each generated string, check if it is balanced according to the rules.
- 3Step 3: Keep track of the minimum number of insertions needed to achieve a balanced string.
solution.py21 lines
1# Full working Python code
2from itertools import combinations
3
4def min_insertions_brute(s):
5 def is_balanced(s):
6 count = 0
7 for char in s:
8 if char == '(': count += 1
9 elif char == ')': count -= 1
10 if count < 0: return False
11 return count == 0
12
13 min_insertions = float('inf')
14 for i in range(len(s) + 1):
15 for j in range(i + 1, len(s) + 2):
16 for insert in combinations('()' * (len(s) - i), j - i):
17 new_s = s[:i] + ''.join(insert) + s[i:]
18 if is_balanced(new_s):
19 min_insertions = min(min_insertions, len(insert))
20 return min_insertions
21Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.