Stack: Length of the longest valid substring

You are given a string, you need to find the length of longest valid parenthesis.

Input : ((()

Output : 2

For the solution, we will use one stack and follow below steps:

1. Initialize stack with -1.

2. When we encounter “(” then we push the index of “(” into the stack.

3. When we encounter “)”, then we pop the element from the stack.

a. At that time, if the stack is empty, then we push the index of “)” as the base index.

b. If it is not empty, then find the length of the current valid parenthesis by taking the difference betweem the current index and the top of the stack.

Then if the current length is more than the result, then update the result.

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;

int get_max_length(string str)
{
    int n = str.length();
 
    stack<int> stk;
    stk.push(-1);
 
    // Initialize result
    int result = 0;
 
    for (int i = 0; i < n; i++)
    {
        if (str[i] == '(')
            stk.push(i);
         
        else
        {

            if (!stk.empty())
            {
                stk.pop();
            }
             
            //if stack is not empty
            if (!stk.empty())
                result = max(result, i - stk.top());
 
            //if stack is empty
            else
                stk.push(i);
        }
    }
 
    return result;
}
 
int main()
{
    string str = "((()()";
   
    cout << "The max length of the valid parenthesis is " <<get_max_length(str) << endl;

    return 0;
}

Output:

 

The max length of the valid parenthesis is 4