Given a string s containing only '(' and ')', determine the minimum number of…
20262025
Given a string s containing only '(' and ')', determine the minimum number of parentheses that must be inserted at arbitrary positions so that the resulting string is valid.
A parentheses string is valid when:
every opening parenthesis has a matching closing parenthesis;
every closing parenthesis has an earlier matching opening parenthesis;
all pairs are properly nested.
Input Format
A single non-empty string s consisting only of '(' and ')'.
Output Format
Print one integer: the minimum number of insertions needed to make s valid.
Examples
Input | Output | Explanation |
|---|---|---|
(()( | 2 | Two opening parentheses remain unmatched, so two closing parentheses are inserted. |
))) | 3 | Each closing parenthesis lacks an earlier opening parenthesis, so three opening parentheses are inserted. |
)()() | 1 | The first closing parenthesis is unmatched, so one opening parenthesis is inserted before it. |
Constraints
1 ≤ |s| ≤ 100,000
s[i] is either '(' or ')' for every valid index i.
Attempted by 6 students.
Show answer & explanation
Concept
While scanning from left to right, maintain balance: the number of unmatched opening parentheses seen so far. A closing parenthesis can consume one unmatched opening parenthesis only when balance is positive.
If a closing parenthesis appears when balance is zero, an opening parenthesis must be inserted before it. After the scan, every remaining unmatched opening parenthesis needs one inserted closing parenthesis.
Application
Initialize balance = 0 and insertions = 0.
For each '(' character, increase balance by 1.
For each ')' character, decrease balance when balance > 0; otherwise increase insertions by 1, representing an opening parenthesis inserted immediately before this ')'.
After all characters are processed, leave balance unchanged. The minimum insertion count is insertions + balance because each unmatched '(' needs one ')'.
For the concrete input )()(, the state changes as follows:
Character | Balance after processing | Required opening insertions |
|---|---|---|
) | 0 | 1 |
( | 1 | 1 |
) | 0 | 1 |
( | 1 | 1 |
The scan contributes 1 required opening parenthesis and leaves balance = 1, so the total is 1 + 1 = 2.
Complexity
Time: O(n), because each character is processed once.
Extra space: O(1), because only two counters are maintained.
Cross-check
Each time a closing parenthesis arrives with balance = 0, the running prefix deficit increases by one and forces one opening insertion. After those deficits are repaired, each unmatched opening parenthesis left at the end forces one closing insertion. The algorithm performs exactly these unavoidable insertions, so no smaller answer is possible.
Result
Print insertions + balance; do not add balance into insertions beforehand.