1541. Minimum Insertions to Balance a Parentheses String
SourceBiweekly Contest 32 Q3DifficultyMediumRating1759
Description
You are given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if it can be formed using the following rules:
- The empty string is balanced.
- If
Ais balanced, then'('+A+'))'is balanced. - If
AandBare balanced, then their concatenation is balanced.
In other words, every left parenthesis '(' must have a corresponding pair of two consecutive right parentheses '))' that comes after it, and every right parenthesis must belong to exactly one such matching pair.
For example, "())", "())(())))" and "(())())))" are balanced, while ")()", "()))" 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 '(' is matched with two consecutive ')', but the first '(' has only one matching ')'. We need to insert one more ')' at the end to make the string "(())))", which is balanced.
Example 2:
Input: s = "())"
Output: 0
Explanation:
The string is already balanced because its '(' is followed by two consecutive ')', and both right parentheses belong to that matching pair.
Example 3:
Input: s = "))())("
Output: 3
Explanation:
Insert '(' at the beginning to match the first '))', and insert '))' at the end to match the last '('. Three insertions are needed in total.
Constraints:
1 <= s.length <= 105sconsists of'('and')'only.
Solutions
Solution 1
Thinking
A valid string pairs each '(' with two consecutive ')' . \(n\le 10^5\), so repeatedly rescanning insertion sites is the wrong tool; one greedy pass is enough.
Keep \(x\), the number of unmatched left parentheses. A '(' increments \(x\). On a ')', insert a mate if the next character is not also ')' . Then either insert a '(' when \(x=0\), or consume one pending left. After the scan, each leftover left needs two right parentheses.
The greedy strategy is the same as above; the Rust version only changes the scanning mechanics: a Peekable iterator consumes the matching second ')' with next_if_eq, so no explicit index bounds check is needed.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | |