Leetcode 1541. Minimum Insertions to Balance a Parentheses String
Problem Explanation
The problem requires you to check if a string of parentheses is balanced or not. A balanced parentheses string in this problem follows these two criteria:
- Any left parenthesis '(' must have a corresponding two consecutive right parentheses '))'.
- Left parenthesis '(' must go before the corresponding two consecutive right parentheses '))'.
You can insert parentheses at any position of the string to make it balanced, and your goal is to return the minimum number of insertions needed to make the string balanced.
For example:
- For string "(()))", it's almost balanced but missing a ')' to complete the first '('. We need to insert a ')' at the end making the string as "(())))" which is now balanced. So, the number of insertions required is 1.
- For string "())", it's already balanced. So, no insertion required and the result is 0.
Solution Approach
The approach is simple. We maintain three counters:
neededRight
to indicate the number of ')' needed to form the pair with '('.missingLeft
to store number of '(' needed when we encounter ')' without '('.missingRight
to store number of ')' to make the pair for '(' if we encounter '))' quickly.
We loop through the string:
- When '(' is encountered, we check if
neededRight
is odd (after incrementingneededRight
by 2 for each '('). If it is, it means we have encountered a '))' pair quicker than expected, so we incrementmissingRight
and decrementneededRight
. - When ')' is encountered, we decrement
neededRight
. IfneededRight
is negative, it means a ')' is encountered without equivalent '('. So we incrementmissingLeft
(meaning, we need one '(') andneededRight
is increased by 2 (since we need to account for the other missing ')').
Finally, we return the sum of neededRight
, missingLeft
and missingRight
as the minimum number of insertions required to make the string balanced.
Python Solution
1 2python 3class Solution: 4 def minInsertions(self, s: str) -> int: 5 neededRight = 0 6 missingLeft = 0 7 missingRight = 0 8 9 for c in s: 10 if c == '(': 11 if neededRight % 2 == 1: 12 missingRight += 1 13 neededRight -= 1 14 neededRight += 2 15 else: # c == ')' 16 neededRight -= 1 17 if neededRight < 0: 18 missingLeft += 1 19 neededRight += 2 20 21 return neededRight + missingLeft + missingRight
Java Solution
1 2java 3class Solution { 4 public int minInsertions(String s) { 5 int neededRight = 0; 6 int missingLeft = 0; 7 int missingRight = 0; 8 9 for (char c : s.toCharArray()) { 10 if (c == '(') { 11 if (neededRight % 2 == 1) { 12 missingRight++; 13 neededRight--; 14 } 15 neededRight += 2; 16 } else { 17 neededRight--; 18 if (neededRight < 0) { 19 missingLeft++; 20 neededRight += 2; 21 } 22 } 23 } 24 25 return neededRight + missingLeft + missingRight; 26 } 27}
C# Solution
1 2csharp 3public class Solution { 4 public int MinInsertions(string s) { 5 int neededRight = 0; 6 int missingLeft = 0; 7 int missingRight = 0; 8 9 foreach (char c in s) { 10 if (c == '(') { 11 if (neededRight % 2 == 1) { 12 missingRight++; 13 neededRight--; 14 } 15 neededRight += 2; 16 } else { 17 neededRight--; 18 if (neededRight < 0) { 19 missingLeft++; 20 neededRight += 2; 21 } 22 } 23 } 24 25 return neededRight + missingLeft + missingRight; 26 } 27}
C++ Solution
1 2cpp 3class Solution { 4public: 5 int minInsertions(string s) { 6 int neededRight = 0, missingLeft = 0, missingRight = 0; 7 8 for (char c : s) { 9 if (c == '(') { 10 if (neededRight % 2 == 1) { 11 missingRight++; 12 neededRight--; 13 } 14 neededRight += 2; 15 } else { 16 neededRight--; 17 if (neededRight < 0) { 18 missingLeft++; 19 neededRight += 2; 20 } 21 } 22 } 23 24 return neededRight + missingLeft + missingRight; 25 } 26};
JavaScript Solution
1 2javascript 3class Solution { 4 minInsertions(s) { 5 let neededRight = 0; 6 let missingLeft = 0; 7 let missingRight = 0; 8 9 for (let i = 0; i < s.length; i++) { 10 let c = s.charAt(i); 11 if (c == '(') { 12 if (neededRight % 2 == 1) { 13 missingRight++; 14 neededRight--; 15 } 16 neededRight += 2; 17 } else { 18 neededRight--; 19 if (neededRight < 0) { 20 missingLeft++; 21 neededRight += 2; 22 } 23 } 24 } 25 26 return neededRight + missingLeft + missingRight; 27 } 28}
Ruby Solution
Similar to the previous solutions, in Ruby, we also check for each character of the string. If it is an open parenthesis, then we increment neededRight
by 2 and check if we've encountered a ))
pair earlier than expected. If it is a closing parenthesis, we decrement neededRight
by 1 and check if we have encountered it without a corresponding open parenthesis.
The missingLeft
, neededRight
and missingRight
variables keep track of different parenthesis requirements to balance the string.
1 2ruby 3class Solution 4 def minInsertions(s) 5 neededRight = 0 6 missingLeft = 0 7 missingRight = 0 8 9 s.chars.each do |c| 10 if c == '(' 11 if neededRight % 2 == 1 12 missingRight += 1 13 neededRight -= 1 14 end 15 neededRight += 2 16 else 17 neededRight -= 1 18 if neededRight < 0 19 missingLeft += 1 20 neededRight += 2 21 end 22 end 23 end 24 25 return neededRight + missingLeft + missingRight 26 end 27end
The minInsertions(s)
method returns the minimum number of insertions needed to make the string balanced.
Conclusion
Balancing parentheses in a string requires careful tracking of when the parentheses are expected to close and when there is a lack of opening or closing parentheses to pair them up. The number of required right, missing left, and missing right parentheses must be summed up to find the number of total insertions needed to balance the string fully.
The solution approach described here applies to several different programming languages, including Python, Java, JavaScript, Ruby, C#, and C++. It uses an algorithm that calculates the minimum number of insertions needed to balance the parentheses in the provided string, irrespective of the initial state of balance or imbalance.
The solutions demonstrated here can be readily used in real-world applications that need to process, validate, or interpret expressions, formulas, or text involving balanced parentheses.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.