LeetCode Q32: Longest Valid Parentheses (hard)

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.

	class Solution {
	public:
	int longestValidParentheses(string s) {
	vector<int> v(s.length(), 0);
	stack<int> myStack;
	for(int i=0; i<s.length(); i++){
	if(!myStack.empty()){
	int j = myStack.top();
	if(s[i]==')'&&s[j]=='('){
	myStack.pop();
	v[i]=1;
	v[j]=1;
	}else{
	myStack.push(i);
	}
	}else
	myStack.push(i);
	}
	int maxl=INT_MIN;
	int len = 0;
	for(int i=0; i<v.size(); i++){
	if(v[i]==1)
	len++;
	else{
	maxl=max(len, maxl);
	len=0;
	}
	}
	maxl = max(maxl, len);
	return maxl==INT_MIN? 0:maxl;
	}
	};

view raw Q32-2.cpp hosted with ❤ by GitHub

• Optimal solution, 8ms.

	class Solution {
	public:
	int longestValidParentheses(string s) {
	stack<int> stk;
	stk.push(-1);
	int maxL=0;
	for(int i=0;i<s.size();i++)
	{
	int t=stk.top();
	if(t!=-1&&s[i]==')'&&s[t]=='(')
	{
	stk.pop();
	maxL=max(maxL,i-stk.top());
	}
	else
	stk.push(i);
	}
	return maxL;
	}
	};

view raw Q32LongestValidParenthesis2.cpp hosted with ❤ by GitHub