Shortest Regular Brackets Sequence

Interview

Time limit1sMemory limit128 MB

Summary

Given a string of brackets, find the length of the shortest regular bracket sequence that contains it as a subsequence.

Level: Medium7 of 10
Topics: Dynamic programming, Intervals, String, Implementation
Solved: No attempts yet

Problem

A regular brackets sequence is defined as follows.

The empty sequence is a regular brackets sequence.
If $S$ is a regular brackets sequence, then $(S)$ and $[S]$ are also regular brackets sequences.
If $A$ and $B$ are regular brackets sequences, then their concatenation $AB$ is also a regular brackets sequence.

For example, all of the following are regular brackets sequences:

(), [], (()), ([]), ()[], ()[()]

None of the following are regular brackets sequences:

(, [, ), )(, ([)], ([(]

You are given a string consisting of the four characters (, ), [, and ]. Among all regular brackets sequences that contain the given string as a subsequence, find the shortest one and report its length.

Here, a string $a_1 a_2 \dots a_n$ is a subsequence of a string $b_1 b_2 \dots b_m$ if there exist indices $1 \le i_1 < i_2 < \dots < i_n \le m$ such that $a_j = b_{i_j}$ for every $1 \le j \le n$ .

Input

The first line contains a string made up only of the characters (, ), [, and ]. The string has length at most $100$ and contains no other characters. The string may be empty (an empty line), which represents the empty sequence.

Output

Print a single integer: the length of the shortest regular brackets sequence that contains the given string as a subsequence.

Examples3

Example 1
Input
```
([(]
```
Expected output
```
6
```
Example 2
Input
```
()
```
Expected output
```
2
```
Example 3
Input
```
([)]
```
Expected output
```
6
```