Length of longest valid substring

Given a string which contains opnening and closing paranthesis, write a function that will find the longest valid parenthesis substring

Example

INPUT
s = "(())())"

OUTPUT
6
"(())()" is the longest valid paranthesis substring in above example

Time Complexity : O(n)

Algorithm

1. Create an empty stack and push -1 to it. -1 is to provide base case for next valid string

2. create a variable 'res' to store the output

3. Traverse all characters from start to end

    a. If the character is '(', then push current index to the stack
    b. Else,
        i) Pop an element from the stack
        ii) If stack is not empty,  then find length of current valid  substring by taking difference between current index and top of the stack. If current length is more than result, then update the result.
        iii) If stack is empty, push current index as base for next valid substring.

4. return res

Implementation of the algorithm

s = "(())"
push -1 into stack, and initialize res = 0

i = 0, s[0] = '(',  push 0 into stack, now stack = [-1,0]
i = 1, s[1] = '(',  push 1 into stack, now stack = [-1,0,1]
i = 2, s[2] = ')', pop() so now stack = [-1,0]
res = max(res, i - stack.top()) = max(0, 2-0) = max(0,2) = 2
i = 3, s[3] = ')', pop() so now stack = [-1]
res = max(res, i - stack.top()) = max(2, 3-(-1)) = max(2,4) = 4

Therefore, longest length is = res = 4. 

C++ Program

#include<bits/stdc++.h>
using namespace std;
 
int maxLength(string s)
{
    int n = s.length();
 
    // Create a stack and push -1 as initial index to it.
    stack<int> stck;
    stck.push(-1);
 
    // Initialize res
    int res = 0;
 
    // Traverse all characters of given string
    for (int i=0; i<n; i++)
    {
        // If opening bracket, push index of it
        if (s[i] == '(')
          stck.push(i);
 
        else // If closing bracket, i.e.,s[i] = ')'
        {
            // Pop the previous opening bracket's index
            stck.pop();
 
            // Check if this length formed with base of
            // current valid substring is more than max 
            // so far
            if (!stck.empty())
                res = max(res, i - stck.top());
 
            // If stack is empty. push current index as 
            // base for next valid substring (if any)
            else stck.push(i);
        }
    }
 
    return res;
}
 

int main()
{
    string s = "()(())";
    cout << maxLength(s) << endl ;
 
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top