Minimum Insertions to Balance a Parentheses String - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
1541. Minimum Insertions to Balance a Parentheses String
Medium
30 Points
String
Stack
Greedy
Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:
In other words, we treat '(' as an opening parenthesis and '))' as a closing parenthesis.
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.
Examples
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.
Example 2
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.
1541. Minimum Insertions to Balance a Parentheses String
Medium
30 Points
String
Stack
Greedy
Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:
In other words, we treat '(' as an opening parenthesis and '))' as a closing parenthesis.
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.
Examples
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.
Example 2
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 '('.