All Tracks Data Structures Stacks Basics of Stacks Problem

Minimum Add to Make Parentheses Valid

No tags

Problem

Editorial

Analytics

Discussions NEW

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

It is the empty string, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

SAMPLE INPUT

()))((

SAMPLE OUTPUT

Explanation

The given string can be balanced to "((()))(())", requiring 4 more paranthesis minimum.

Time Limit: 5.0 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors