1541. Minimum Insertions to Balance a Parentheses String
Problem Description
The given problem involves a string s
which contains only parentheses – specifically, the characters '(' and ')'. The objective is to make the string balanced according to the following rules:
- A left parenthesis '(' must be followed by two consecutive right parentheses '))'.
- The order must be maintained, i.e., for every '(', the corresponding '))' must come after it.
We can add parentheses anywhere in the string to balance it. The task is to find the minimum number of insertions required to balance the string.
Examples of balanced strings as per these rules are: "())", "())(())))", and "(())())))". On the other hand, strings like ")()", "()))", and "(()))" are not balanced as per the rules described.
Intuition
The intuition behind the solution is to iterate through the string, keeping track of how many opening and closing parentheses are needed to balance the string as we go.
We maintain two counters:
x
: to count the number of opening parentheses '(' we have seen that need right parentheses '))'.ans
: to count the number of insertions needed to balance the string.
While iterating through the string:
- When we encounter an '(', we increment
x
because we anticipate needing two more ')' to balance it later. - When we encounter a ')', we have two cases:
- If it's followed by another ')', this means we found a pair '))', so we decrement
x
as we have matched one opening '(' with two closing '))'. - If it's not followed by another ')', we have a single ')', so we add one to
ans
as we need to insert an additional ')' to balance the string, and then decrementx
.
- If it's followed by another ')', this means we found a pair '))', so we decrement
- If
x
is zero and a closing ')' without a matching '(' is found, we need to insert an opening '(' before it, so we add one toans
. - After processing the closing parentheses, if
x
is greater than zero, it means there are unmatched '(' pending, so we need to add two ')' for each of them. Thus, we incrementans
byx
shifted to the left by 1 (which is equivalent to multiplyingx
by 2).
This solution ensures that we make the minimum number of insertions required to balance the string by only adding parentheses when necessary to make the string adhere to the balancing rules.
Solution Approach
The implementation of the solution involves a greedy approach to satisfy the conditions for a balanced parentheses string, as mentioned earlier. The algorithm can be detailed as follows:
-
Initialize Two Counters: We have two counters
ans
andx
, whereans
keeps track of the number of insertions needed andx
keeps track of the number of unmatched opening parentheses that are yet to be paired with a closing parentheses. -
Iterating Over the String: We iterate over each character in the string using a
while
loop, indexed byi
. -
Handling Opening Parentheses '(': When we encounter an opening parenthesis, we increment
x
by 1, as we need to find or insert two consecutive closing parentheses to balance it. -
Handling Closing Parentheses ')':
- If the current character is a ')', we first check whether it forms a pair with the next character (i.e., if it is followed by another ')'). If yes, we increment
i
by 1 to skip the next character since we have a complete pair '))', and then we decrementx
. - If there is no ')' following the current one, we increment
ans
as we need to insert an additional ')' to have a pair '))'. We then checkx
: ifx
is zero (meaning we have an excess of closing parentheses), we incrementans
again to insert a '(' before the existing ')'. Otherwise, ifx
is not zero, we simply decrementx
.
- If the current character is a ')', we first check whether it forms a pair with the next character (i.e., if it is followed by another ')'). If yes, we increment
-
Handle Unmatched Opening Parentheses: After the loop, if we still have unmatched opening parentheses (i.e., if
x
is greater than zero), it means we need to insert two ')' for each. We do this by addingx << 1
(which is equivalent tox * 2
) toans
. -
Returning the Result: Finally, the
ans
counter now contains the minimal number of insertions needed to balance the string according to the problem constraints, and we return this value.
The key points in this greedy algorithm are:
- Efficiently keeping track of the number of parentheses we need to insert.
- Balancing insertions only when necessary to fulfill the condition that each '(' is followed by two ')'.
- Using bitwise shift
x << 1
as a quick operation to double thex
value, which is equivalent to adding two closing parentheses for every unmatched '(' at the end of the iteration.
By following this approach, we can guarantee the minimum number of insertions needed to achieve a balanced string.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Consider the string s = "(()))("
. We need to go through the string and determine how many insertions are required to make this string balanced according to the rules. Let's walk through the solution step-by-step:
-
Initialize two counters:
ans
= 0 (counts the total number of insertions needed)x
= 0 (counts the number of open parentheses '(' that need to be paired with closing ones '))')
-
Iterating over the string:
- Index
i = 0
, characters[i] = '('
:- We increment
x
because this opening parenthesis needs two closing ones. - State after this step:
ans
= 0,x
= 1
- We increment
- Index
i = 1
, characters[i] = '('
:- We increment
x
again for another unmatched opening parenthesis. - State after this step:
ans
= 0,x
= 2
- We increment
- Index
i = 2
, characters[i] = ')'
:- This right parenthesis could be paired with one from the previous two, but since it should be paired with two, we need another right parenthesis.
- We increment
ans
to insert one ')' character and decrementx
. - State after this step:
ans
= 1,x
= 1
- Index
i = 3
, characters[i] = ')'
:- This right parenthesis forms a valid pair with the previous '('.
- We decrement
x
. - State after this step:
ans
= 1,x
= 0
- Index
i = 4
, characters[i] = ')'
:- Since
x
is zero, this right parenthesis is extra and lacks a corresponding '('. - We increment
ans
to add an opening '(' before it. - State after this step:
ans
= 2,x
= 0
- Since
- Index
i = 5
, characters[i] = '('
:- We have an opening parenthesis that needs two closing ones.
- Increment
x
. - State after this step:
ans
= 2,x
= 1
- Index
-
Handle unmatched opening parentheses:
- The iteration ends with
x
greater than zero; hence, we need to insert two ')' for the unmatched '('. - Update
ans
byx << 1
which is equivalent to adding two ')' characters for the last '('. ans
=ans
+ (x
* 2) = 2 + (1 * 2) = 4
- The iteration ends with
-
Returning the result:
- With
ans
equalling to 4, we conclude that four insertions are needed to make the string "(()))("
balanced according to the given rules.
- With
The final balanced string after insertions would look like "(())())(())".
Solution Implementation
1class Solution:
2 def min_insertions(self, s: str) -> int:
3 # 'balance' keeps track of the balance of the parentheses
4 # 'insertions_needed' will be the answer, representing the minimum insertions needed
5 insertions_needed = balance = 0
6 i, n = 0, len(s) # 'i' is the current position, 'n' is the length of the string
7
8 while i < n: # Iterate through the string
9 if s[i] == '(': # If the current character is an opening parenthesis
10 balance += 1 # Increase balance
11 else: # If the current character is a closing parenthesis
12 # Check if there's a consecutive closing parenthesis
13 if i < n - 1 and s[i + 1] == ')':
14 i += 1 # Move to the next character as we've found a pair "))"
15 else:
16 # If a pair wasn't found, one insertion is needed
17 insertions_needed += 1
18 # If there is no unmatched opening parenthesis
19 if balance == 0:
20 # We need an insertion for an opening parenthesis
21 insertions_needed += 1
22 else:
23 # Otherwise, use one unmatched opening to balance a pair "))"
24 balance -= 1
25 i += 1 # Move to the next character
26
27 # After processing the entire string, we might have unmatched opening parentheses
28 # Each of these needs two insertions to be balanced (one opening parenthesis needs "))")
29 insertions_needed += balance * 2
30
31 return insertions_needed # Return the total number of insertions needed
32
1public class Solution {
2 public int minInsertions(String s) {
3 // Initialize a counter for the insertions needed and a counter for open parentheses
4 int insertionsCount = 0, openParensCount = 0;
5 int n = s.length();
6
7 // Iterate through each character in the string
8 for (int i = 0; i < n; ++i) {
9 char currentChar = s.charAt(i);
10
11 // If we encounter an open parenthesis, we increment the open parentheses count
12 if (currentChar == '(') {
13 ++openParensCount;
14 } else {
15 // Check if the next character is also a close parenthesis
16 if (i < n - 1 && s.charAt(i + 1) == ')') {
17 // If it is, we move the index ahead since this is a valid pair of close parentheses
18 ++i;
19 } else {
20 // If it's not, we need an extra insertion to complete a pair
21 ++insertionsCount;
22 }
23
24 // If there are no open parentheses to match, we need an insertion for an open parenthesis
25 if (openParensCount == 0) {
26 ++insertionsCount;
27 } else {
28 // Otherwise, we found a matching pair, so decrement the open parentheses count
29 --openParensCount;
30 }
31 }
32 }
33
34 // After processing all characters, we may have unmatched open parentheses.
35 // Each one requires two insertions to form a complete "()()"
36 insertionsCount += openParensCount << 1;
37
38 // Return the total number of insertions needed to balance the string
39 return insertionsCount;
40 }
41}
42
1class Solution {
2public:
3 int minInsertions(string s) {
4 int additionalInsertionsNeeded = 0; // This will count the insertions needed to balance the string.
5 int openBracketsCount = 0; // This will keep track of the count of '(' characters seen.
6 int stringLength = s.size(); // Length of the input string.
7
8 for (int i = 0; i < stringLength; ++i) {
9 if (s[i] == '(') {
10 // If the current character is '(', increment the open brackets count.
11 ++openBracketsCount;
12 } else {
13 // If the current character is ')', check if the next character is also ')'.
14 if (i < stringLength - 1 && s[i + 1] == ')') {
15 // If yes, skip the next character as '))' is a valid pair.
16 ++i;
17 } else {
18 // If no, one additional insertion is needed as we expect ')'.
19 ++additionalInsertionsNeeded;
20 }
21
22 // Now, we check if there is an open bracket ('(') available to match the closing bracket.
23 if (openBracketsCount == 0) {
24 // If not, we need to insert an additional '(' before the current ')'.
25 ++additionalInsertionsNeeded;
26 } else {
27 // If there is an open bracket, pair it with the current closing bracket.
28 --openBracketsCount;
29 }
30 }
31 }
32
33 // After processing all characters,
34 // we still might have some '(' brackets open which need to be closed.
35 // For each '(', we need to insert '))' to balance.
36 additionalInsertionsNeeded += openBracketsCount * 2;
37
38 return additionalInsertionsNeeded; // Return the count of insertions needed.
39 }
40};
41
1function minInsertions(s: string): number {
2 let additionalInsertionsNeeded = 0; // This will count the insertions needed to balance the string.
3 let openBracketsCount = 0; // This will keep track of the count of '(' characters seen.
4 let stringLength = s.length; // Length of the input string.
5
6 for (let i = 0; i < stringLength; ++i) {
7 if (s[i] === '(') {
8 // If the current character is '(', increment the open brackets count.
9 ++openBracketsCount;
10 } else {
11 // If the current character is ')', check if the next character is also ')'.
12 if (i < stringLength - 1 && s[i + 1] === ')') {
13 // If yes, skip the next character as '))' is a valid pair.
14 ++i;
15 } else {
16 // If no, one additional insertion is needed because we expect ')' to make a pair.
17 ++additionalInsertionsNeeded;
18 }
19
20 // Now, check if there is an open bracket ('(') available to match the current closing bracket.
21 if (openBracketsCount === 0) {
22 // If not, insert an additional '(' before the current ')' to balance.
23 ++additionalInsertionsNeeded;
24 } else {
25 // If there is an open bracket, pair it with the current closing bracket.
26 --openBracketsCount;
27 }
28 }
29 }
30
31 // After processing all characters,
32 // there might still be some '(' brackets open which need to be closed.
33 // For each '(', we need to insert '))' to balance.
34 additionalInsertionsNeeded += openBracketsCount * 2;
35
36 return additionalInsertionsNeeded; // Return the total count of insertions needed.
37}
38
Time and Space Complexity
The given Python code aims to find the minimum number of insertions required to balance a string of parentheses.
Time Complexity:
The time complexity of the function is determined by how it iterates through the input string:
- There's a single loop through the input string, which traverses each character exactly once.
- Inside the loop, operations are constant-time: arithmetic, if checks, and a single potential increment of the loop variable
i
. - There is no nested looping or function calls that depend on the size of input inside the loop.
Considering the length of the string as n
, the total number of steps is proportional to n
. Therefore, the time complexity of the code is O(n)
.
Space Complexity:
The space complexity is determined by the amount of extra space used besides the input itself. In the case of this function:
ans
,x
,i
, andn
are simple integer variables that occupy constant space.- There is no use of any data structures that can grow with the input size.
- There are no recursive calls that would add to the call stack space.
Since the space used does not depend on the input size and remains constant, the space complexity of the code is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.