Largest Balanced String
Tag(s):

## Algorithms, Bracket Matching, Regular sequence, String Manipulation

Problem
Editorial
Analytics
• An empty sequence is balanced.

• A sequence of the form (A) or [A] or {A} is balanced if A is balanced.

• A sequence of the form AB is balanced if A and B both are balanced.

You are given a string A, consisting of '(', ')', '[', ']', '{' and '}' only. You have to find the maximum length of the balanced string after performing some valid operation(s).

Valid operations are

• Remove any character from string A

• Swap any two adjacent characters of string A

You can perform these valid operations in any order and any numbers of times.

Input Format

The first line of input contains an integer T, denoting the number of the test cases.
Each of the next T lines contains a single string A.

Output Format

For each case, print the maximum length of the balanced string in a separate line.

Input Constraints

$1 \le T \le 100$

$1 \le |A| \le 5000; |A| \; denotes \; string \; length$

SAMPLE INPUT
5
(){}()[]
))[]]((
{{{{{{{}
[]{}]
{}}

SAMPLE OUTPUT
8
6
2
4
2

Explanation
(){}()[]: This is already balanced so ans = 8.
))[]](( : By performing few conseqcutive swap you can move last two char to the front.
String will look like (())[]]. Then you can remove last character, so final balanced
string length is 6.
{{{{{{{}: Remove first 6 characters ans = 2.
[]{}]   : Remove last character ans = 4.
{}}     : Remove last character ans = 2.
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

ThoughtWorks Coding Challenge for Women

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting