***Longest Regular Bracket Sequence(dp)

Longest Regular Bracket Sequence

This is yet another problem dealing with regular bracket sequences.

We should remind you that a bracket sequence is called regular, if by inserting «+» and «1» into it we can get a correct mathematical expression. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not.

You are given a string of «(» and «)» characters. You are to find its longest substring that is a regular bracket sequence. You are to find the number of such substrings as well.

Input

The first line of the input file contains a non-empty string, consisting of «(» and «)» characters. Its length does not exceed 106.

Output

Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing "0 1".

Sample test(s)

input

)((())))(()())

output

6 2

input

))(

output

0 1

-----------------------------------------------------------EDITORIAL-----------------------------------------

First of all, for each closing bracket in our string let's define 2 values:

• d[j] = position of corresponding open bracket, or INT_MAX (MEANS AT INFINITY IN RIGHT ) if closing bracket doesn't belong to any regular bracket sequence.
•  c[j] = position of earliest(EARLIEST BALANCED) opening bracket, such that substring s(c[j], j) (both boundaries are inclusive) is a regular bracket sequence. Let's consider c[j] to be INT_MAX if closing bracket doesn't belong to any regular bracket sequence.

It can be seen, that c[j] defines the beginning position of the longest regular bracket sequence(BY JOINING SOME SEQUENCE ALSO LIKE ()()(()) , which will end in position j. So, having c[j] answer for the problem can be easily calculated.

Both d[j] and c[j] can be found with following algorithm, which uses stack.

1. Iterate through the characters of the string.
2. If current character is opening bracket, put its position into the stack.
3. If current character is closing bracket, there are 2 subcases:

• Stack is empty - this means that current closing bracket doesn't have corresponding open one. Hence, both d[j] and c[j] are equal to  INT_MAX.
• Stack is not empty - we will have position of the corresponding open bracket on the top of the stack - let's put it to d[j] and remove this position from the stack. Now it is obvious, that c[j] is equal at least to d[j]. 
• But probably, there is a better value for c[j](SOME EARLIER CONTINUOUS BALANCE). To find this out, we just need to look at the position d[j] - 1(IT CAN BE EITHER A CLOSING OR A OPENING , IF A OPENING  THAN CANT BE INCLUDED OR IF CLOSING THAN  WE CAN INCLUDE TILL C[] OF THIS CLOSING ) . If there is a closing bracket at this position, and c[d[j] - 1] is not INT_MAX, than we have 2 regular bracket sequences s(c[d[j] - 1] TO  d[j] - 1)  +  s(d[j], j),  which can be concatenated into one larger regular bracket sequence. So we put c[j] to be c[d[j] - 1] for this case.

-----------------------

FOR CLARITY SEE THE CODE 

-------------------------------------------CODE----------------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

char arr[10000000];

int count;

int c[1000100],d[1000100];

int main()

{

      cin>>arr;

     int n=strlen(arr);

      int f=0,b=0; 

      for(int i=0;i<=n;i++)

       {

         c[i]=INT_MAX;

         d[i]=INT_MAX;

   }

    stack<int> s;

    for(int i=0;i<n;i++)

     {

      if(arr[i]==')')

       {

  if(!s.empty())

  {

   int top=s.top();

   s.pop();

   d[i]=top;

   c[i]=top;// AT LEAST 

    c[i]=min(c[d[i]-1],c[i]);// AS LEFT AS POSSIBLE WILL BE THE LONGEST 

                             //  CHAR AR J-1 CAN BE ( ALSO IN THAT CASE IT WILL  GIVE INT_MAX , SOO                                  // WILL NOT INCLUDED

 

  }

  }

  else s.push(i);

 }

 int ans=0,count=1;

 for(int i=0;i<n;i++)

  {

    if(arr[i]==')')

     {

 if(i-c[i]+1>ans)

        {

   ans=i-c[i]+1;

          count =1;

  }

  else if(i-c[i]+1==ans)

   {

     count ++;

   }

}

  }

       cout<<ans;

   if(ans==0)

    {

       cout<<" "<<1<<endl;

}

else cout<<" "<<count<<endl;

}