Beautiful Bracket String (Paid Article and Add Time Complexity)

Concepts Used:

Stack

Difficulty Level:

Medium.

Problem Statement :

Find the minimum number of replacements required to make the given string of braces balanced.

See original problem statement here

Example:

Input:
}{
{}{}{}
{{{}

Output:
1. 2
2. 0
3. 1

Solving Approach:

1.This is very similar to the problem where we had to check where the given string of braces is balanced.

2.According to data structures and algorithms tutorials, This question is just a modification of it.

3.Unlike that problem,here you have to push the closing brace ‘}’ also to the stack if the top of the stack of the stack already contains a closing brace.

4.Once done with traversing the entire list, traverse the stack until it’s empty.

  1. If the two topmost elements are same, add 1 to the counter ,for example – ({,{); (},}).

  2. If the two topmost elements are different, add 2 to the counter if the combination is {,}. because this gives an unbalanced string and both the braces need to be replaced.

  3. If the two topmost elements are different, add 0 to the counter if the combination is },{ because it is already balanced.

Solutions:

#include <stdio.h>
#include<stdlib.h>
#include<string.h>
int get(char a,char b){
    if(a == b)
        return 1;
    if(a == '{' && b == '}')
        return 2;
    return 0;
    }
    int main(int argc, char const *argv[])
    {
    char s[100005];
    int c, k = 1;
    while(1)
    {
        scanf("%s",s);

        if(s[0] == '-')
            return 0;

        printf("%d. ",k++);
        c = 0;
        char ch;
    int n=strlen(s);
        char stack[100005];int top=-1;

        for(int i = 0; i < n; i++)
        {
            if(top==-1 || s[i] == '{')
                stack[++top]=s[i];
            else
            {
                if( stack[top] == '{' )
                    top--;
                else
                    stack[++top]=s[i];
            }
        }

        while(top!=-1)
        {
            ch = stack[top];
            top--;
            c += get(ch, stack[top]);   
            top--;
        }
        printf("%d\n",c);
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
int get(char a,char b){
    if(a == b)
        return 1;
    if(a == '{' and b == '}')
        return 2;
    return 0;
}
int main(int argc, char const *argv[]){
    string s;
    int c, k = 1;
    while(1)
    {
        cin>>s;

        if(s[0] == '-')
            return 0;

        cout<<k++<<". ";
        c = 0;
        char ch;

        stack<char> q;

        for(int i = 0; i < s.length(); i++)
        {
            if(q.empty() || s[i] == '{')
                q.push(s[i]);
            else
            {
                if( q.top() == '{' )
                    q.pop();
                else
                    q.push(s[i]);
            }
        }

        while(!q.empty())
        {
            ch = q.top();
            q.pop();
            c += get(ch, q.top());  
            q.pop();
        }
        cout<<c<<endl;
    }
    return 0;
}
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);

              int j=1;

    while( j>0){

          String str=sc.next();
          if(str.charAt(0)=='-'){
          break;
          }
          else{
         System.out.print(j+". ");

          beauty_Bracket(str);

          }
          j++; 
          System.out.println("");
    }
    }

    static void beauty_Bracket(String str){
        int count=0;  
       Stack<Character> stk = new Stack<>();
       int n= str.length();
      for(int i=0;i<n;i++)
      {
          if(str.charAt(i)=='{'){
              stk.push(str.charAt(i));
          }
          else if(str.charAt(i)=='}'){
              if(!stk.empty())
              stk.pop();

              else{
              count++;
              stk.push('{');
              }
          }
      }
     if(stk.size()!=0)
        {
            count+=stk.size()/2;
        }

    System.out.print(count);

     }
}
Previous post Small Group
Next post One more GCD sum

Leave a Reply

Your email address will not be published. Required fields are marked *