Algotree > Algorithms > Stack > Longest Valid Parentheses

Longest Valid Parentheses

Given : A string containing ‘(’ and ‘)’ characters.
Objective : To find the length of the longest valid parentheses substring.

Example :
1. In the string " ( ( ) ( " the longest valid parentheses substring is " ( ( ) ( " of length 2.
2. In the string " ( ) ( ) ( ( ) ( " the longest valid parentheses substring is " ( ) ( ) ( ( ) ( " of length 4.

C++ : Program to find the longest valid parentheses substring

#include<iostream>
#include<string>
#include<stack>
#include<vector>

using namespace std;

int Length_LongestValid_Parentheses (string str) {

    stack<int> stk;
    stk.push(-1);

    int maxlen = 0;

    for (int index=0; index < str.size(); index++) {
        if (str.at(index) == '(') {
            stk.push(index);
        } else if (str.at(index) == ')') {
            stk.pop();
            if (stk.empty()) {
                stk.push(index);
            } else {
                if (maxlen < index - stk.top()) {
                    maxlen = index - stk.top();
                }
            }
        }
    }
    return maxlen;
}

int main() {

    vector<string> vec = {"((()", "()()()", "()(()", "))())", "(", "(((())))()(()()()"};

    for (const auto& str : vec) {
        cout << "String : " << str << endl;
        cout << "Length of longest valid parantheses : " << Length_LongestValid_Parentheses(str) << endl << endl;
    }
    return 0;
}

Output

String : ((()
Length of longest valid parantheses : 2

String : ()()()
Length of longest valid parantheses : 6

String : ()(()
Length of longest valid parantheses : 2

String : ))())
Length of longest valid parantheses : 2

String : (
Length of longest valid parantheses : 0

String : (((())))()(()()()
Length of longest valid parantheses : 10