Skip to main content

Count the Reversals

Problem Statement:

Given a string S consisting only of opening and closing curly brackets '{' and '}' find out the minimum number of reversals required to make a balanced expression.
Input
The first line of input contains an integer T denoting the number of test cases. Then T test cases
follow. 
The first line of each test case contains a string S consisting only of { and }.

Output
Print out minimum reversals required to make S balanced.If it cannot be balanced, then print -1.

Constraints
1 <= T <= 100
0 <   S  <= 50
Examples 
Input
4
}{{}}{{{
{{}}}}
{{}{{{}{{}}{{
{{{{}}}}
Output
3
1
-1
0
Expected Complexity
Time:   O(n)
Space: O(n)

Code:
import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++)
{
  
   int count=0;
   String s=sc.next();
   Stack <Character>h=new Stack<Character>();
   int flag=0;
   if(s.length()%2!=0)
   {
       flag=1;
   }
   else {
   for(int j=0;j<s.length();j++)
   {
       char ch=s.charAt(j);
       if(ch=='{')
       {
           h.push(ch);
       }
       else if(ch=='}')
       {
           if(!h.empty() && h.peek()=='{')
           {
               h.pop();
           }
           else{
               h.push(ch);
           }
       }
   }
   
   while(!h.empty())
   {
       char x=h.pop();
       if(x=='{')
       {
           if(!h.empty() && h.peek()=='{')
           {
               count=count+1;
               h.pop();
           }
           else if(!h.empty() && h.peek()=='}')
           {
               count=count+2;
               h.pop();
           }
           else {
               flag=1;
           }
       }
       else if(x=='}')
       {
           if(!h.empty() && h.peek()=='}')
           {
               count=count+1;
               h.pop();
           }
           else if(!h.empty() && h.peek()=='{')
           {
               h.pop();
           }
           else {
               flag=1;
           }
       }
   }   
}
if(flag==0){
   System.out.println(count);
}
else{
   System.out.println("-1");
}
}
}
}

Comments

Post a Comment

Popular posts from this blog

A Very Basic yet important question in a life of a software developer

 Processes Vs Threads Process:  It is an execution unit where a program runs. The OS helps to create, schedule, and terminates the processes which is used by CPU. The other processes created by the main process are called child process. A process operations can be controlled with the help of PCB(Process Control Block). PCB contains all the crucial information related to processing like process id, priority, state, and contents CPU register, etc. Important properties of the process: - Creation of each process requires separate system calls for each process. - It is an isolated execution entity and does not share data and information. - Processes use the IPC(Inter-Process Communication) mechanism for communication that significantly increases the number of system calls. - Process management takes more system calls. - A process has its stack, heap memory, and data map. Thread:   A process can have multiple threads, all executing at the same time. A thread is lightw...
Post a Comment
Read more

CheatSheet for Searching Algorithms

CheatSheet for Searching Algorithms 1. Linear Search int search(int arr[], int x) { int n = arr.length; for(int i = 0; i < n; i++) { if(arr[i] == x) return i; } return -1; } The time complexity of above algorithm is O(n). 2. Binary Search // Returns location of key, or -1 if not found // Returns location of key, or -1 if not found int BinarySearch(int A[], int l, int r, int key) { int m; while( l <= r ) { m = l + (r-l)/2; if( A[m] == key ) // first comparison return m; if( A[m] < key ) // second comparison l = m + 1; else r = m - 1; } return -1; } The time complexity of Binary Search Theta(log(n)) Auxiliary Space: O(1) in case of iterative implementation. In case of recursive implementation, O(Logn) recursion call stack space. 3. The Ubiquitous Binary Search // Invariant: A[l] <= key and A[r] > key // Boundar...
Post a Comment
Read more