Editorial-CFRS0C

editorial
1

Problem Link::valid string
Difficulty:: Medium
setter:: @sanjeev2001
Code::
Simple::

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        int n=s.length();
        int mx=INT_MIN,cnt=0,tmp=0;
        int open=0,close=0,mx=0;
       for(int i=0;i<s.size();i++)
       {
           if(s[i]=='{')
           {
               open++;
           }
           else 
           {
               close++;
           }
           if(open==close) 
           {
               mx=max(mx,close+open);
           }
           else if(close>open) 
           {
               close=open=0;
           }
       }
       
       open=close=0;
       
         for(int i=s.size()-1;i>=0;i--)
         {
           if(s[i]=='{')
           {
               open++;
           }
           else 
           {
               close++;
           }
           if(open==close) 
           {
               mx=max(mx,close+open);
           }
           else if(open>close)  
           {
               close=open=0;
           }
       }
        cout<<mx<<endl;
    }
}

Using Stack::

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        stack<int> st;
        st.push(-1);
        int ans = 0;
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='{')
            {
                st.push(i);
            }
            else
            {
                st.pop();
                if(st.empty())
                {
                    st.push(i);
                }
                else
                {
                    ans = max(ans,i-st.top());
                }
            }
        } 
        cout<<ans<<endl;
    }
}