CorrectingParenthesization | Topcoder Archive

Problem Statement

Given a string of parentheses, we must turn it into a well formed string by changing as few characters as possible (we cannot delete or insert characters).

There are 3 kinds of parentheses: regular (), brackets [] and curly brackets {}. Each pair has an opening ('(', '[' and '{' respectively) and a closing (')', ']' and '}') character.

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), [s] and {s} are well formed strings.
If s and t are well formed strings, the concatenation st is a well formed string.

As examples, "([{}])", "" and "(){}[]" are well formed strings and "([}]", "([)]" and "{" are malformed strings.

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

Definition

Class:: CorrectingParenthesization
Method:: getMinErrors
Parameters:: String
Returns:: int
Method signature:: int getMinErrors(String s)
(be sure your method is public)

Notes

Changing a character is selecting one position in the string and changing the character in that position to any other parentheses character.

Constraints

s will have between 0 and 50 characters, inclusive.
s will have an even number of characters.
Each character of s will be '(', '[', '{', ')', ']' or '}'.

Examples

```
"([{}])()[]{}"
```
```
Returns: 0
```
This is already well formed.
```
"([)]"
```
```
Returns: 2
```
With two changes you can get "([])" (there are other ways with the same number of changes).
```
"([{}[]"
```
```
Returns: 1
```
Simply changing the second character will give you "(){}[]".

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.