Misha was playing with Balanced Brackets alone. Mykhailo also wanted to play the game with her, so he comes up and asks her a question.
Misha is allowed to chose a sub-sequence (i.e. not necessarily contiguous substring) of brackets. AFTER chosing a the sub-sequence, she is allowed to re-arrange it (if needed) such that this chosen sub-sequence (after rearrangement) is balanced. Find the maximum length of this sub-sequence. (Please note that the resulting sub-sequence , after rearrangement MUST be balanced.)
For each testcase, the maximum possible length of balanced string.
import java.util.*;
import java.util.Scanner;
public class Main {
static boolean Balanced(String expr)
{
Deque<Character> stack
= new ArrayDeque<Character>();
for (int i = 0; i < expr.length(); i++)
{
char x = expr.charAt(i);
if (x == '(' || x == '[' || x == '{')
{
stack.push(x);
continue;
}
if (stack.isEmpty())
return false;
char check;
switch (x) {
case ')':
check = stack.pop();
if (check == '{' || check == '[')
return false;
break;
case '}':
check = stack.pop();
if (check == '(' || check == '[')
return false;
break;
case ']':
check = stack.pop();
if (check == '(' || check == '{')
return false;
break;
}
}
return (stack.isEmpty());
}
public static void main(String[] args)
{
Scanner input=new Scanner(System.in);
System.out.print("Enter the number of test cases: ");
int T=input.nextInt();
for(int i=0;i<T;i++){
System.out.println("Enter the string of brackets: ");
String S = input.next();
int N=S.length();
System.out.println("The length of the string is: "+N);
if (Balanced(S))
System.out.println("Balanced ");
else
System.out.println("You chose unBalanced string ");}
}
}
Comments
Leave a comment