## 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

int maxl=0;

int i=0;

int t=0;

while (i

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.

*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 i−s+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 i−s.top().

You can do it easily in perl with three lines:

$input = ‘)()())’;$ct++ while ($input=~/\(\)/g);

print $ct*2;

hi Kamal ,

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