Algotree > Algorithms > Stack > Longest Valid Parentheses Using Stack

Longest Valid Parentheses Using Stack

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.

Algorithm

Idea is to use a stack to find the length of the longest valid parentheses. As we traverse the string from the beginning till the end, we do the following

Whenever we get an opening bracket "(", we push the index of "(" onto the stack.
Whenever we get a closing bracket ")", we pop the previously pushed index of "(" (if any) from the stack. Whatever index that now remains at the top of the stack would give us the length.
Thus length = current_index - index_that_now_remains_at_the_top_after_popping_the_index_of_the_matching_closing_bracket

Note: Before we begin running the algorithm, we push a -1 onto the stack.

Consider the below
Example 1: string : ( )

Stack	Character	Index	Operation	Length
-1 ( Initial value at stack top before run )				0
-1	(	0	Push 0 onto stack	0
0 -1	)	1	Pop 0 from the stack & calculate the max length	Max length = 1 - ( - 1 ) = 2

Example 2: string : ( ( ) )

Stack	Character	Index	Operation	Length
-1 ( Initial value at stack top before run )				0
-1	(	0	Push 0 onto stack	0
0 -1	(	1	Push 1 onto stack 1	0
1 0 -1	)	2	Pop 1 from the stack & calculate the max length	2 - ( 0 ) = 2
0 -1	)	3	Pop 0 from the stack & calculate the max length	Max length = 3 - ( -1 ) = 4

Program to find the longest valid parentheses substring using stack

#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

from collections import deque

def Length_LongestValid_Parentheses (string) -> int:

    stack = deque()
    stack.appendleft(-1)

    maxlen = 0

    for index in range(len(string)) :
        if (string[index] == '(') :
            stack.appendleft(index) 
        elif (string[index] == ')') :
            stack.popleft()
            if (len(stack) == 0) : # If stack is empty, just push the current index
                stack.appendleft(index)
            else : # If stack is not empty, calculate the max valid parenthesis length
                if (maxlen < index - stack[0]) :
                    maxlen = index - stack[0]
    return maxlen

def main() :

    parantheseslist = ["()()()", "", "((()", "()(()", "))())", "()", "(((())))()(()()()", "(", ")"]

    for p in parantheseslist :
        print("String : " + p)
        print("Length of longest valid parantheses : " + str(Length_LongestValid_Parentheses(p)) + "\n")

if __name__ == "__main__" :
    main()

Output

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

String : 
Length of longest valid parantheses : 0

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

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

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

String : ()
Length of longest valid parantheses : 2

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

String : (
Length of longest valid parantheses : 0

String : )
Length of longest valid parantheses : 0

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

class Parentheses {

    int Longest_Valid_Parentheses (String str) {

        Stack<Integer> stk = new Stack<Integer>();
        int maxlen = 0;
        stk.push(-1);
        
        for (int index=0; index < str.length(); index++) {
            if (str.charAt(index) == '(') {
                stk.push(index);
            } else if (str.charAt(index) == ')') {
                stk.pop();
                if (stk.isEmpty()) {
                    stk.push(index);
                } else {
                    if (maxlen < index - stk.peek()) {
                        maxlen = index - stk.peek();
                    }
                }
            }
        }
        return maxlen;
    }

    public static void main (String args[]) {

        List<String> parentheses_strings = Arrays.asList( "((()", "()(()", "))())", "()()()", "", "()", "(((())))()(()()()", "(", ")" );
        Parentheses p = new Parentheses();
        for (String str : parentheses_strings) {
            System.out.println("\nString : " + str);
            System.out.println("Length of longest valid parentheses : " + p.Longest_Valid_Parentheses(str));
        }
    }   
}

Output

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

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

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

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

String : 
Length of longest valid parentheses : 0

String : ()
Length of longest valid parentheses : 2

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

String : (
Length of longest valid parentheses : 0

String : )
Length of longest valid parentheses : 0