Not As Hard As It Seems
Sakib and Shamim are good friends. As Sakib is a little naughty, every night before exam he disturbs Shamim. One day Shamim got an idea to get rid of Sakib. Shamim gave him a sequence of parentheses and brackets, and told him to determine the maximum length of a valid subsequence.
For example, [] , ([]) are valid subsequences but (], [)(] are not. Remember an empty sequence is also a valid subsequence.
Since Sakib was intelligent he solved the problem easily and continued disturbing Shamim. Can you solve it too?
Input
You will be given multiple strings of parentheses and brackets, one in each line. The length of each string will be no more than 106.
Output
For each such string, you will have to determine the maximum length of valid subsequence.
Sample
| Input | Output |
|---|---|
[]() ([])() | 2 4 |
The valid subsequences of maximum length for the first string are | |
