1541. Minimum Insertions to Balance a Parentheses String LeetCode Solution
In this guide, you will get 1541. Minimum Insertions to Balance a Parentheses String LeetCode Solution with the best time and space complexity. The solution to Minimum Insertions to Balance a Parentheses String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Insertions to Balance a Parentheses String
Given a parentheses string s containing only the characters ‘(‘ and ‘)’. A parentheses string is balanced if:
Any left parenthesis ‘(‘ must have a corresponding two consecutive right parenthesis ‘))’.
Left parenthesis ‘(‘ must go before the corresponding two consecutive right parenthesis ‘))’.
In other words, we treat ‘(‘ as an opening parenthesis and ‘))’ as a closing parenthesis.
For example, “())”, “())(())))” and “(())())))” are balanced, “)()”, “()))” and “(()))” are not balanced.
You can insert the characters ‘(‘ and ‘)’ at any position of the string to balance it if needed.
Return the minimum number of insertions needed to make s balanced.
Example 1:
Input: s = “(()))”
Output: 1
Explanation: The second ‘(‘ has two matching ‘))’, but the first ‘(‘ has only ‘)’ matching. We need to add one more ‘)’ at the end of the string to be “(())))” which is balanced.
Input: s = “())”
Output: 0
Explanation: The string is already balanced.
Example 3:
Input: s = “))())(”
Output: 3
Explanation: Add ‘(‘ to match the first ‘))’, Add ‘))’ to match the last ‘(‘.
Constraints:
1 <= s.length <= 105
s consists of '(' and ')' only.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
1541. Minimum Insertions to Balance a Parentheses String LeetCode Solution in C++
class Solution {
public:
int minInsertions(string s) {
int neededRight = 0; // Increment by 2 for each '('.
int missingLeft = 0; // Increment by 1 for each missing '('.
int missingRight = 0; // Increment by 1 for each missing ')'.
for (const char c : s)
if (c == '(') {
if (neededRight % 2 == 1) {
// e.g. "()(..."
++missingRight;
--neededRight;
}
neededRight += 2;
} else if (--neededRight < 0) { // c == ')'
// e.g. "()))..."
++missingLeft;
neededRight += 2;
}
return neededRight + missingLeft + missingRight;
}
}; /* code provided by PROGIEZ */
1541. Minimum Insertions to Balance a Parentheses String LeetCode Solution in Java
class Solution {
public int minInsertions(String s) {
int neededRight = 0; // Increment by 2 for each '('.
int missingLeft = 0; // Increment by 1 for each missing '('.
int missingRight = 0; // Increment by 1 for each missing ')'.
for (final char c : s.toCharArray())
if (c == '(') {
if (neededRight % 2 == 1) {
// e.g. "()(..."
++missingRight;
--neededRight;
}
neededRight += 2;
} else if (--neededRight < 0) { // c == ')'
// e.g. "()))..."
++missingLeft;
neededRight += 2;
}
return neededRight + missingLeft + missingRight;
}
} // code provided by PROGIEZ
1541. Minimum Insertions to Balance a Parentheses String LeetCode Solution in Python
class Solution:
def minInsertions(self, s: str) -> int:
neededRight = 0 # Increment by 2 for each '('.
missingLeft = 0 # Increment by 1 for each missing '('.
missingRight = 0 # Increment by 1 for each missing ')'.
for c in s:
if c == '(':
if neededRight % 2 == 1:
# e.g. '()(...'
missingRight += 1
neededRight -= 1
neededRight += 2
else: # c == ')'
neededRight -= 1
if neededRight < 0:
# e.g. '()))...'
missingLeft += 1
neededRight += 2
return neededRight + missingLeft + missingRight # code by PROGIEZ
