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.

2 thoughts on “Longest Valid Parentheses leetcode solution”

Leave a Reply

Your email address will not be published. Required fields are marked *