Given a string s containing only '(' and ')', determine the minimum number of…
PYQ TCS NQT 2026PYQ IBM Hiring Assessment 2025
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 7 students.
Sign up free to check your answer
Sign up freeLoading lesson…

