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 free

Explore the full course: Coding For Placement

Loading lesson…