# Longest Valid Parentheses leetcode solution

## Longest Valid Parentheses leetcode solution

Longest Valid Parentheses leetcode solution

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses
substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

int longestValidParentheses(string s) {
if (s.size()<2) {return 0;} stack > st;
int maxl=0;
int i=0;
int t=0;
while (i tmp = st.top();
st.pop();
if (tmp.first=='(‘){
if (!st.empty())
{
maxl=max(maxl,(i-st.top().second));
}
else{
maxl=max(maxl,i-t+1); // else till go to last invalid state
}
}
}
}
i++;
}
return maxl;
}

The above solution takes O(n) time duration.

Consider the following cases when hitting a ‘ ) ‘. Denote the index of current ‘ ) ‘ as i.
• Stack is empty. This means we found an invalid substring like ‘( ) ) ‘ and we set s=i+1 as the next index of ‘)’ since no substring contains this ‘)’ will be a valid one.
• Stack is not empty but there is only one ‘(‘ in the stack. This means we found a complete valid substring like ‘( ( ) )’ or ‘( ) ( )’ starting from s. The length of substring is is+1.
• The stack is not empty and there is more than one ‘( ‘ in the stack. This means we found a partial valid substring like ‘( ( ) ( ) ‘, you can see that s should be the index of the top element in the stack after popping a ‘( ‘. To get the index easily, we push the index of ‘ ( ‘ into the stack directly. The length of the substring is is.top().
This algorithm runs in O(n) time and O(n) space in worst case.

# Resolving technical problems:

We provide Remote Technical Support from Monday to Sunday, 7:00PM to 1:00 AM

Mail your problem details at writeulearn@gmail.com along with your mobile numberand we will give you a call for further details. We usually attend your problems within 60 minutes and solve it in maximum 2 days.

## 2 thoughts on “Longest Valid Parentheses leetcode solution”

1. Kamal Nayan says:

You can do it easily in perl with three lines:
$input = ‘)()())’;$ct++ while ($input=~//g); print$ct*2;

1. tarry says:

hi Kamal ,
thats right,Perl is very much efficient in text and string manipulation i.e. regular expressions

This site uses Akismet to reduce spam. Learn how your comment data is processed.