Connection Status:
Competition Arena > MissingParentheses

MissingParentheses

SRM 521 · 2011-05-25 · by soul-net

SRM 521 · 2011-05-25 · by soul-net · Greedy
Class Name: MissingParentheses
Return Type: int
Method Name: countCorrections
Arg Types: (string)
Problem Statement

Problem Statement

Given a string of parentheses, you must turn it into a well formed string by inserting as few parentheses as possible, at any position (you cannot delete or change any of the existing parentheses).

A well formed string of parentheses is defined by the following rules:

  • The empty string is well formed.
  • If s is a well formed string, (s) is a well formed string.
  • If s and t are well formed strings, their concatenation st is a well formed string.
As examples, "(()())", "" and "(())()" are well formed strings and "())(", "()(" and ")" are malformed strings.

Given a String par of parentheses, return the minimum number of parentheses that need to be inserted to make it into a well formed string.

Constraints

  • par will contain between 1 and 50 characters, inclusive.
  • Each character of par will be an opening or closing parenthesis, i.e., '(' or ')'.
Examples
0)
"(()(()"
Returns: 2

The string below is a possible well formed string you can get to by inserting the two closing parentheses marked. (())(()) ^ ^

1)
"()()(()"
Returns: 1

You can fix the string by inserting a single closing parenthesis at the end.

2)
"(())(()())"
Returns: 0

The input string is well formed, so no insertion is needed.

3)
"())(())((()))))()((())))()())())())()()()"
Returns: 7
4)
"()"
Returns: 0

Submissions are judged against all 125 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MissingParentheses with a public method int countCorrections(string par) · 125 test cases · 2 s / 256 MB per case

Submitting as anonymous